25. MFCS 2000: Bratislava, Slovakia

Invited Talks

• Silvano Dal-Zilio, Andrew D. Gordon:
  Region Analysis and a pi-Calculus wiht Groups. 1-20
  
• James H. Davenport:
  Abstract Data Types in Computer Algebra. 21-35
  
• Camil Demetrescu, Giuseppe F. Italiano:
  What Do We Learn from Experimental Algorithmics? 36-51
  
• Radu Grosu:
  And/Or Hierarchies and Round Abstraction. 52-63
  
• Edith Hemaspaandra, Lane A. Hemaspaandra:
  Computational Politics: Electoral Systems. 64-83
  
• Phokion G. Kolaitis, Moshe Y. Vardi:
  0-1 Laws for Fragments of Existential Second-Order Logic: A Survey. 84-98
  
• Jan van Leeuwen, Jirí Wiedermann:
  On Algorithms and Interaction. 99-113
  
• Shmuel Zaks:
  On the Use of Duality and Geometry in Layouts for ATM Networks. 114-131
  

Contributed Papers

• Farid M. Ablayev, Aida Gainutdinova:
  On the Lower Bounds for One-Way Quantum Automata. 132-140
  
• Samson Abramsky, Marina Lenisa:
  Axiomatizing Fully Complete Models for ML Polymorphic Types. 141-151
  
• Klaus Ambos-Spies:
  Measure Theoretic Completeness Notions for the Exponential Time Classes. 152-161
  
• Lali Barrière, Josep Fàbrega:
  Edge-Bisection of Chordal Rings. 162-171
  
• David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien:
  Equation Satisfiability and Program Satisfiability for Finite Monoids. 172-181
  
• Jean Berstel, Luc Boasson:
  XML Grammars. 182-191
  
• Therese C. Biedl, Brona Brejová, Tomás Vinar:
  Simplifying Flow Networks. 192-201
  
• Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang:
  Balanced k-Colorings. 202-211
  
• Frank S. de Boer, Marcello M. Bonsangue:
  A Compositional Model for Confluent Dynamic Data-Flow Networks. 212-221
  
• Beate Bollig:
  Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication. 222-231
  
• Patricia Bouyer, Catherine Dufourd, Emmanuel Fleury, Antoine Petit:
  Expressiveness of Updatable Timed Automata. 232-242
  
• Thomas Buchholz, Andreas Klein, Martin Kutrib:
  Iterative Arrays with Small Time Bounds. 243-252
  
• Rostislav Caha, Petr Gregor:
  Embedding Fibonacci Cubes into Hypercubes with Omega(2^cn) Faulty Nodes. 253-263
  
• Arturo Carpi, Aldo de Luca:
  Periodic-Like Words. 264-274
  
• Olivier Carton, Wolfgang Thomas:
  The Monadic Theory of Morphic Infinite Words and Generalizations. 275-284
  
• Francesc Comellas, Margarida Mitjana, Lata Narayanan, Jaroslav Opatrny:
  Optical Routing of Uniform Instances in Tori. 285-294
  
• Clelia de Felice:
  Factorizing Codes and Schützenberger Conjectures. 295-303
  
• Mariangiola Dezani-Ciancaglini, Furio Honsell, Yoko Motohama:
  Compositional Characterizations of lambda-Terms Using Intersection Types. 304-313
  
• Stefan Dobrev:
  Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks. 314-322
  
• Arnaud Durand, Miki Hermann, Phokion G. Kolaitis:
  Subtractive Reductions and Complete Problems for Counting Complexity Classes. 323-332
  
• Todd Ebert, Heribert Vollmer:
  On the Autoreducibility of Random Sequences. 333-342
  
• Zoltán Ésik:
  Iteration Theories of Boolean Functions. 343-352
  
• Alain Finkel, Grégoire Sutre:
  An Algorithm Constructing the Semilinear Post^* for 2-Dim Reset/Transfer VASS. 353-362
  
• Dimitris Fotakis, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis:
  NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. 363-372
  
• Philippa Gardner, Lucian Wischik:
  Explicit Fusions. 373-382
  
• Jan Friso Groote, Jaco van de Pol:
  State Space Reduction Using Partial tau-Confluence. 383-393
  
• Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung:
  Reducing the Number of Solutions of NP Functions. 394-404
  
• Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P. S. Thiagarajan:
  Regular Collections of Message Sequence Charts. 405-414
  
• Markus Holzer, Pierre McKenzie:
  Alternating and Empty Alternating Auxiliary Stack Automata. 415-425
  
• Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, Richard A. Kemmerer:
  Conter Machines: Decidable Properties and Applications to Verification Problems. 426-435
  
• Kazuo Iwama, Akihiro Matsuura, Mike Paterson:
  A Family of NFA's Which Need 2ⁿ -alpha Deterministic States. 436-445
  
• Klaus Jansen, Lorant Porkolab:
  Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring. 446-455
  
• Ondrej Klíma, Jirí Srba:
  Matching Modulo Associativity and Idempotency Is NP-Complete. 456-466
  
• Sven Kosub:
  On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems. 467-476
  
• Daniel Král:
  Algebraic an Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization. 477-487
  
• Werner Kuich:
  Formal Series over Algebras. 488-496
  
• Orna Kupferman, Moshe Y. Vardi:
  µ-Calculus Synthesis. 497-507
  
• Grégory Lafitte, Jacques Mazoyer:
  The Infinite Versions of LOGSPACE != P Are Consistent with the Axioms of Set Theory. 508-517
  
• Ruggero Lanotte, Andrea Maggiolo-Schettini:
  Timed Automata with Monotonic Activities. 518-527
  
• Vadim V. Lozin:
  On a Generalization of Bi-Complement Reducible Graphs. 528-538
  
• Olivier Ly:
  Automatic Graphs and Graph D0L-Systems. 539-548
  
• Sabrina Mantaci, Vincent D. Blondel, Jean Mairesse:
  Bilinear Functions and Trees over the (max, +) Semiring. 549-558
  
• Angelo Montanari, Alberto Policriti, Matteo Slanina:
  Derivability in Locally Quantified Modal Logics via Translation in Set Theory. 559-568
  
• Ugo Montanari, Marco Pistore:
  pi-Calculus, Structured Coalgebras, and Minimal HD-Automata. 569-578
  
• David Peleg:
  Informative Labeling Schemes for Graphs. 579-588
  
• Holger Petersen:
  Separation Results for Rebound Automata. 589-598
  
• Giovanni Pighizzini:
  Unary Pushdown Automata and Auxiliary Space Lower Bounds. 599-608
  
• Jaco van de Pol, Hans Zantema:
  Binary Decision Diagrams by Shard Rewriting. 609-618
  
• Leonor Prensa Nieto, Javier Esparza:
  Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL. 619-628
  
• Alexander Moshe Rabinovich, Shahar Maoz:
  Why so Many Temporal Logics Climb up the Trees? 629-639
  
• Steffen Reith, Heribert Vollmer:
  Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems. 640-649
  
• Petr Savický, Detlef Sieling:
  A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism. 650-659
  
• Thomas Schwentick:
  On Diving in Trees. 660-669
  
• Miki Tanaka:
  Abstract Syntax and Variable Binding for Linear Binders. 670-679
  
• Tanguy Urvoy:
  Regularity of Congruential Graphs. 680-689
  
• Klaus Wich:
  Sublinear Ambiguity. 690-698
  
• Hiroaki Yamamoto:
  An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions. 699-708