Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS'99 Szklarska Poreba, Poland, September 6-10, 1999 ProceedingsMiroslaw Kutylowski, Leszek Pacholski, Tomasz Wierzbicki 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. |
Contents
| 1 | |
| 12 | |
The Arithmetical Hierarchy of Real Numbers | 23 |
Compression Techniques | 34 |
Efficiency of Fast Parallel Pattern Searching in Highly Compressed Texts | 48 |
Foundations of Programming | 59 |
Foundations of Modular SOS | 70 |
Message Sequence Graphs and Decision Problems on Mazurkiewicz Traces | 81 |
Functional Programming | 187 |
Automata | 209 |
Average State Complexity of Operations on Unary Automata | 231 |
Algorithms and Complexity | 251 |
Lower and Upper Bounds for the Problem of Page Replication in Ring | 273 |
Logic | 291 |
On the Structure of the Monadic Logic of the Binary Tree | 310 |
Counting Problems | 332 |
Model Checking | 87 |
Complexity and Algorithms | 91 |
Complexity | 92 |
The Complexity of the Extended GCD Problem | 103 |
Complexity Results for Confluence Problems | 114 |
Is Your Model Checker on Time? | 125 |
Model Checking and HigherOrder Recursion | 149 |
New Perspectives in Distributed Computing | 170 |
On Plain and Hereditary HistoryPreserving Bisimulation | 354 |
Graph Algorithms | 376 |
On Minimum Edge Ranking Spanning Trees | 398 |
Football Elimination Is Hard to Decide Under the 3PointRule | 410 |
A Foundation of Programming a Multitape Quantum Turing Machine | 430 |
Type Reconstruction for Functional Programs with Subtyping over | 443 |
Other editions - View all
Common terms and phrases
abstract accepted algebra algorithm apply approach approximation assignment assume automata automaton bases belief binary bound branching called checking closed colors communication complexity Computer Computer Science condition connected consider consists construct contains corresponding cover decidable define definition denote described domain edges element equations equivalent example exists extended FBDD finite fixed formula function given gives graph Hence Hilbert basis holds initial input instance integer introduced label language least Lemma length linear LNCS logic matching matroids minimal node Note obtained operation pairs particular path points polynomial positive possible present problem proof Proposition prove real-time reduction relation replace respectively restricted result rules satisfies semantics sequence shown solution steps string structure subset symbol Theorem theory transformation transition tree University variables vector vertex