Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS’99 Szklarska Poręba, Poland, September 6–10,1999 Proceedings

Christiane Frougny (auth.), Mirosław Kutyłowski, Leszek Pacholski, Tomasz Wierzbicki (eds.)3540664084, 9783540664086

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.

---

Table of contents :
On-Line Addition in Real Base….Pages 1-11
Query Languages for Real Number Databases Based on Descriptive Complexity over R….Pages 12-22
The Arithmetical Hierarchy of Real Numbers….Pages 23-33
The Burrows-Wheeler Transform: Theory and Practice….Pages 34-47
Efficiency of Fast Parallel Pattern Searching in Highly Compressed Texts….Pages 48-58
Computing and Comparing Semantics of Programs in Four-Valued Logics….Pages 59-69
Foundations of Modular SOS….Pages 70-80
Message Sequence Graphs and Decision Problems on Mazurkiewicz Traces….Pages 81-91
On the Complexity of Recognizing the Hilbert Basis of a Linear Diophantine System….Pages 92-102
The Complexity of the Extended GCD Problem….Pages 103-113
Complexity Results for Confluence Problems….Pages 114-124
Is Your Model Checker on Time?….Pages 125-136
Clausal Resolution for CTL….Pages 137-148
Model Checking and Higher-Order Recursion….Pages 149-159
Multiparty Communication Complexity: Very Hard Functions….Pages 160-169
New Perspectives in Distributed Computing….Pages 170-186
An Improved Disjunctive Strictness Analysis for Lazy Functional Languages….Pages 187-197
Unique Fixed Point Induction for McCarthy’s Amb….Pages 198-208
On Some Topological Properties of Linear Cellular Automata….Pages 209-219
Real-Time Language Recognition by One-Way and Two-Way Cellular Automata….Pages 220-230
Average State Complexity of Operations on Unary Automata….Pages 231-240
Fooling Rebound Automata….Pages 241-250
The Complexity of Minimizing FBDDs….Pages 251-261
Efficient Strongly Universal and Optimally Universal Hashing….Pages 262-272
Lower and Upper Bounds for the Problem of Page Replication in Ring Networks….Pages 273-283
Language-Based Security….Pages 284-298
An Algebraic Approach to Knowledge Representation….Pages 299-309
On the Structure of the Monadic Logic of the Binary Tree….Pages 310-320
A New Space Bound for the Modal Logics K4, KD4 and S4….Pages 321-331
On Approximating the Number of Bases of Exchange Preserving Matroids….Pages 332-342
The Semantic Foundations of a Compositional Proof Method for Synchronously Communicating Processes….Pages 343-353
On Plain and Hereditary History-Preserving Bisimulation….Pages 354-365
Approximating Weak Bisimulation on Basic Process Algebras….Pages 366-375
Edge Coloring of Bipartite Graphs with Constraints….Pages 376-386
An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover….Pages 387-397
On Minimum Edge Ranking Spanning Trees….Pages 398-409
Football Elimination Is Hard to Decide Under the 3-Point-Rule….Pages 410-418
Generalized Regular Counting Classes….Pages 419-429
A Foundation of Programming a Multi-tape Quantum Turing Machine….Pages 430-441
A Type Discipline for Solving Year 2000 Problems in COBOL Programs….Pages 442-442
Type Reconstruction for Functional Programs with Subtyping over a Lattice of Atomic Types….Pages 443-453