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

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