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.

Includes supplementary material: sn.pub/extras

Klappentext
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.

Inhalt
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.- 01 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 NPComplete.- 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.