Mathematical Foundations of Computer Science 2000: 25th International Symposium, MFCS 2000 Bratislava, Slovakia, August 28 – September 1, 2000 Proceedings

Silvano Dal Zilio, Andrew D. Gordon (auth.), Mogens Nielsen, Branislav Rovan (eds.)3540679014, 9783540679011

This book constitutes the refereed proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000, held in Bratislava/Slovakia in August/September 2000. The 57 revised full papers presented together with eight invited papers were carefully reviewed and selected from a total of 147 submissions. The book gives an excellent overview on current research in theoretical informatics. All relevant foundational issues, from mathematical logics as well as from discrete mathematics are covered. Anybody interested in theoretical computer science or the theory of computing will benefit from this book.

---

Table of contents :
Region Analysis and a π-Calculus with Groups….Pages 1-20
Abstract Data Types in Computer Algebra….Pages 21-35
What Do We Learn from Experimental Algorithmics?….Pages 36-51
And/Or Hierarchies and Round Abstraction….Pages 52-63
Computational Politics: Electoral Systems….Pages 64-83
0–1 Laws for Fragments of Existential Second-Order Logic: A Survey….Pages 84-98
On Algorithms and Interaction….Pages 99-113
On the Use of Duality and Geometry in Layouts for ATM Networks….Pages 114-131
On the Lower Bounds for One-Way Quantum Automata….Pages 132-140
Axiomatizing Fully Complete Models for ML Polymorphic Types….Pages 141-151
Measure Theoretic Completeness Notions for the Exponential Time Classes….Pages 152-161
Edge-Bisection of Chordal Rings….Pages 162-171
Equation Satisfiability and Program Satisfiability for Finite Monoids….Pages 172-181
XML Grammars….Pages 182-191
Simplifying Flow Networks….Pages 192-201
Balanced k -Colorings….Pages 202-211
A Compositional Model for Confluent Dynamic Data-Flow Networks….Pages 212-221
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication….Pages 222-231
Expressiveness of Updatable Timed Automata….Pages 232-242
Iterative Arrays with Small Time Bounds….Pages 243-252
Embedding Fibonacci Cubes into Hypercubes with Ω(2 cn ) Faulty Nodes….Pages 253-263
Periodic-Like Words….Pages 264-274
The Monadic Theory of Morphic Infinite Words and Generalizations….Pages 275-284
Optical Routing of Uniform Instances in Tori….Pages 285-294
Factorizing Codes and Schützenberger Conjectures….Pages 295-303
Compositional Characterizations of λ-Terms Using Intersection Types….Pages 304-313
Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks….Pages 314-322
Subtractive Reductions and Complete Problems for Counting Complexity Classes….Pages 323-332
On the Autoreducibility of Random Sequences….Pages 333-342
Iteration Theories of Boolean Functions….Pages 343-352
An Algorithm Constructing the Semilinear Post for 2-Dim Reset/Transfer VASS….Pages 353-362
NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs….Pages 363-372
Explicit Fusions….Pages 373-382
State Space Reduction Using Partial τ-Confluence….Pages 383-393
Reducing the Number of Solutions of NP Functions….Pages 394-404
Regular Collections of Message Sequence Charts….Pages 405-414
Alternating and Empty Alternating Auxiliary Stack Automata….Pages 415-425
Counter Machines: Decidable Properties and Applications to Verification Problems….Pages 426-435
A Family of NFA’s Which Need 2 n — α Deterministic States….Pages 436-445
Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring….Pages 446-455
Matching Modulo Associativity and Idempotency Is NP—Complete….Pages 456-466
On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems….Pages 467-476
Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization….Pages 477-487
Formal Series over Algebras….Pages 488-496
μ-Calculus Synthesis….Pages 497-507
The Infinite Versions of L og S pace ≠ P Are Consistent with the Axioms of Set Theory….Pages 508-517
Timed Automata with Monotonic Activities….Pages 518-527
On a Generalization of Bi-Complement Reducible Graphs….Pages 528-538
Automatic Graphs and Graph D0L -Systems….Pages 539-548
Bilinear Functions and Trees over the (max, +) Semiring….Pages 549-558
Derivability in Locally Quantified Modal Logics via Translation in Set Theory….Pages 559-568
π-Calculus, Structured Coalgebras, and Minimal HD-Automata….Pages 569-578
Informative Labeling Schemes for Graphs….Pages 579-588
Separation Results for Rebound Automata….Pages 589-598
Unary Pushdown Automata and Auxiliary Space Lower Bounds….Pages 599-608
Binary Decision Diagrams by Shared Rewriting….Pages 609-618
Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL….Pages 619-628
Why so Many Temporal Logics Climb up the Trees?….Pages 629-639
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems….Pages 640-649
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism….Pages 650-659
On Diving in Trees Thomas Schwentick….Pages 660-669
Abstract Syntax and Variable Binding for Linear Binders….Pages 670-679
Regularity of Congruential Graphs….Pages 680-689
Sublinear Ambiguity….Pages 690-698
An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions….Pages 699-708