Mathematical Foundations of Computer Science 2000

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.