Mathematical Foundations of Computer Science 1999

This volume contains papers selected for presentation during the 24th Interna tional Symposium on Mathematical Foundations of Computer Science held on September 6-10, 1999 in Szklarska Por^ba, Poland. The symposium, organized alternately in the Czech Republic, Slovakia, and Poland, focuses on theoretical aspects and mathematical foundations of computer science. The scientific program of the symposium consists of five invited talks given by Martin Dyer, Dexter Kozen, Giovanni Manzini, Sergio Rajsbaum, and Mads Tofte, and 37 accepted papers chosen out of 68 submissions. The volume contains all accepted contributed papers, and three invited papers. The contributed papers have been selected for presentation based on their scientific quality, novelty, and interest for the general audience of MFCS par ticipants. Each paper has been reviewed by at least three independent referees PC members and/or sub-referees appointed by them. The papers were se lected for presentation during a fully electronic virtual meeting of the program committee on May 7, 1999. The virtual PC meeting was supported by software written by Artur Zgoda, Ph.D. student at the University of Wroclaw. The entire communication and access to quite a sensitive database at PC headquarters in Wroclaw was secured by cryptographic protocols based on technology of certificates.

Includes supplementary material: sn.pub/extras

Inhalt
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.- CountingProblems.- 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.