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

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