25. MFCS 2000: Bratislava, Slovakia

Mogens Nielsen, Branislav Rovan (Eds.): Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000, Proceedings. Lecture Notes in Computer Science 1893 Springer 2000, ISBN 3-540-67901-4 BibTeX

@proceedings{DBLP:conf/mfcs/2000,
  editor    = {Mogens Nielsen and
               Branislav Rovan},
  title     = {Mathematical Foundations of Computer Science 2000, 25th International
               Symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September
               1, 2000, Proceedings},
  booktitle = {MFCS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1893},
  year      = {2000},
  isbn      = {3-540-67901-4},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talks

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

Contributed Papers

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