Mathematical Foundations of Computer Science 2000

This volume contains papers selected for presentation at the Silver Jubilee 25th Symposium on Mathematical Foundations of Computer Science | MFCS 2000, held in Bratislava, Slovakia, August 28 { September 1, 2000. MFCS 2000 was organized under the auspices of the Minister of Education of the Slovak Republic, Milan Ft a cnik, by the Slovak Society for Computer Science, and the Comenius University in Bratislava, in cooperation with other institu- ons in Slovakia. It was supported by the European Association for Theoretical Computer Science, the European Research Consortium for Informatics and - thematics, and the Slovak Research Consortium for Informatics and Mathe- tics. The series of MFCS symposia, organized alternately in the Czech Republic, Poland, and Slovakia since 1972, has a well-established tradition. The MFCS symposia encourage high-quality research in all branches of theoretical computer science. Their broad scope provides an opportunity of bringing together spec- lists who do not usually meet at specialized conferences. The previous meetings took place in Jablonna, 1972; Strbsk e Pleso, 1973; Jadwisin, 1974; Mari ansk e L azn e, 1975; Gdansk, 1976; Tatransk a Lomnica, 1977; Zakopane, 1978; Olomouc, 1979; Rydzina, 1980; Strbsk e Pleso, 1981; Prague, 1984; Bratislava, 1986; C- lsbad, 1988; Porabk a-Kozubnik, 1989; Bansk a Bystrica, 1990; Kazimierz Dolny, 1991; Prague, 1992; Gdansk, 1993, Ko sice, 1994; Prague, 1995; Krak ow, 1996; Bratislava, 1997; Brno, 1998; and Szklarska Poreba, 1999.

Invited Talks.- Region Analysis and a ?-Calculus with Groups.- Abstract Data Types in Computer Algebra.- What Do We Learn from Experimental Algorithmics?.- And/Or Hierarchies and Round Abstraction.- Computational Politics: Electoral Systems.- 0–1 Laws for Fragments of Existential Second-Order Logic: A Survey.- On Algorithms and Interaction.- On the Use of Duality and Geometry in Layouts for ATM Networks.- Contributed Papers.- On the Lower Bounds for One-Way Quantum Automata.- Axiomatizing Fully Complete Models for ML Polymorphic Types.- Measure Theoretic Completeness Notions for the Exponential Time Classes.- Edge-Bisection of Chordal Rings.- Equation Satisfiability and Program Satisfiability for Finite Monoids.- XML Grammars.- Simplifying Flow Networks.- Balanced k-Colorings.- A Compositional Model for Confluent Dynamic Data-Flow Networks.- Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.- Expressiveness of Updatable Timed Automata.- Iterative Arrays with Small Time Bounds.- Embedding Fibonacci Cubes into Hypercubes with ?(2cn) Faulty Nodes.- Periodic-Like Words.- The Monadic Theory of Morphic Infinite Words and Generalizations.- Optical Routing of Uniform Instances in Tori.- Factorizing Codes and Schützenberger Conjectures.- Compositional Characterizations of ?-Terms Using Intersection Types.- Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks.- Subtractive Reductions and Complete Problems for Counting Complexity Classes.- On the Autoreducibility of Random Sequences.- Iteration Theories of Boolean Functions.- An Algorithm Constructing the Semilinear Post for 2-Dim Reset/Transfer VASS.- NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs.- Explicit Fusions.- State Space Reduction Using Partial ?-Confluence.- Reducing the Number of Solutions of NP Functions.- Regular Collections of Message Sequence Charts.- Alternating and Empty Alternating Auxiliary Stack Automata.- Counter Machines: Decidable Properties and Applications to Verification Problems.- A Family of NFA’s Which Need 2n — ? Deterministic States.- Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring.- Matching Modulo Associativity and Idempotency Is NP—Complete.- On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems.- Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization.- Formal Series over Algebras.- ?-Calculus Synthesis.- The Infinite Versions of LogSpace ? P Are Consistent with the Axioms of Set Theory.- Timed Automata with Monotonic Activities.- On a Generalization of Bi-Complement Reducible Graphs.- Automatic Graphs and Graph D0L-Systems.- Bilinear Functions and Trees over the (max, +) Semiring.- Derivability in Locally Quantified Modal Logics via Translation in Set Theory.- ?-Calculus, Structured Coalgebras, and Minimal HD-Automata.- Informative Labeling Schemes for Graphs.- Separation Results for Rebound Automata.- Unary Pushdown Automata and Auxiliary Space Lower Bounds.- Binary Decision Diagrams by Shared Rewriting.- Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL.- Why so Many Temporal Logics Climb up the Trees?.- Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems.- A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism.- On Diving in Trees Thomas Schwentick.- Abstract Syntax and Variable Binding for Linear Binders.- Regularity of Congruential Graphs.- Sublinear Ambiguity.- An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions.