Mathematical foundations of computer science 1999 : 24th international symposium, MFCS'99, Szklarska Poręba, Poland, September 6-10, 1999 : proceedings / Mirosław Kutyłowski, Leszek Pacholski, Tomasz Wierzbicki (eds.).

Includes bibliographical references and index.

Print version record.

This book constitutes the refereed proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science, MFCS'99, held in Szklarska Poreba, Poland, in September 1999. The 37 revised full papers presented together with four invited contributions were carefully selected from 68 submissions. The papers are organized in sections on computing over reals, compression techniques, foundations of programming, complexity and algorithms, model checking, distributed computing, functional programming, automata, security, logic, counting problems, processes and bisimulation, graph algorithms, and type theory.

Computing Over Reals -- On-Line Addition in Real Base -- Query Languages for Real Number Databases Based on Descriptive Complexity over R -- The Arithmetical Hierarchy of Real Numbers -- Compression Techniques -- The Burrows-Wheeler Transform: Theory and Practice -- Efficiency of Fast Parallel Pattern Searching in Highly Compressed Texts -- Foundations of Programming -- Computing and Comparing Semantics of Programs in Four-Valued Logics -- Foundations of Modular SOS -- Message Sequence Graphs and Decision Problems on Mazurkiewicz Traces -- Complexity and Algorithms -- On the Complexity of Recognizing the Hilbert Basis of a Linear Diophantine System -- The Complexity of the Extended GCD Problem -- Complexity Results for Confluence Problems -- Model Checking -- Is Your Model Checker on Time? -- Clausal Resolution for CTL -- Model Checking and Higher-Order Recursion -- Distributed Computing -- Multiparty Communication Complexity: Very Hard Functions -- New Perspectives in Distributed Computing -- Functional Programming -- An Improved Disjunctive Strictness Analysis for Lazy Functional Languages -- Unique Fixed Point Induction for McCarthy's Amb -- Automata -- On Some Topological Properties of Linear Cellular Automata -- Real-Time Language Recognition by One-Way and Two-Way Cellular Automata -- Average State Complexity of Operations on Unary Automata -- Fooling Rebound Automata -- Algorithms and Complexity -- The Complexity of Minimizing FBDDs -- Efficient Strongly Universal and Optimally Universal Hashing -- Lower and Upper Bounds for the Problem of Page Replication in Ring Networks -- Security -- Language-Based Security -- Logic -- An Algebraic Approach to Knowledge Representation -- On the Structure of the Monadic Logic of the Binary Tree -- A New Space Bound for the Modal Logics K4, KD4 and S4 -- Counting Problems -- On Approximating the Number of Bases of Exchange Preserving Matroids -- Processes and Bisimulation -- The Semantic Foundations of a Compositional Proof Method for Synchronously Communicating Processes -- On Plain and Hereditary History-Preserving Bisimulation -- Approximating Weak Bisimulation on Basic Process Algebras -- Graph Algorithms -- Edge Coloring of Bipartite Graphs with Constraints -- An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover -- On Minimum Edge Ranking Spanning Trees -- Complexity -- Football Elimination Is Hard to Decide Under the 3-Point-Rule -- Generalized Regular Counting Classes -- A Foundation of Programming a Multi-tape Quantum Turing Machine -- Types: Theory and Applications -- A Type Discipline for Solving Year 2000 Problems in COBOL Programs -- Type Reconstruction for Functional Programs with Subtyping over a Lattice of Atomic Types.