MFCS 2001

26th International Symposium on
Mathematical Foundations of Computer Science

August 27 - 31, 2001
Marianske Lazne, Czech Republic


Accepted Papers

The Program Committee met on May 11-12 in Prague and selected the following 51 papers to be presented at the symposium, out of 118 submissions.
(The papers are ordered alphabetically.)
(H,C,K)-Coloring: Fast, Easy, and Hard Cases
Josep Diaz, Maria Serna, Dimitrios M. Thilikos
A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing
Wolfgang Espelage, Egon Wanke
A Time Hierarchy for Bounded One-Way Cellular Automata
Andreas Klein, Martin Kutrib
Algorithmic information theory and cellular automata dynamics
Julien Cervelle, Bruno Durand, Enrico Formenti
Alignment between two RNA structures
Zhuozhi Wang, Kaizhong Zhang
Analysis Problems for Sequential Dynamical Systems and Communicating State Machines
Chris Barrett, Harry B. Hunt III, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns
Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings
Thomas Erlebach
Automata on linear orderings
Véronique Bruyère, Olivier Carton
Automatic Verification of Recursive Procedures with one Integer Parameter
Ahmed Bouajjani, Peter Habermehl, Richard Mayr
Characterization of context-free languages with polynomially bounded ambiguity
Klaus Wich
Checking Amalgamability Conditions for Casl Architectural Specifications
Bartek Klin, Piotr Hoffman, Andrzej Tarlecki, Lutz Schroeder, Till Mossakowski
Complexity Note on Mixed Hypergraphs
Daniel Kral', Jan Kratochvil, Heinz-Juergen Voss
Computable Versions of Baire's Category Theorem
Vasco Brattka
Computing Reciprocals of Bivariate Power Series
Markus Blaeser
Converting Two-Way Nondeterministic Unary Automata into Simpler Automata
Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini
Exact results for accepting probabilities of quantum automata
Andris Ambainis, Arnolds Kikusts
From Bidirectionality to Alternation
Nir Piterman, Moshe Vardi
Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds
Henrik Brosenne, Matthias Homeister, Stephan Waack
Hierarchy of Monotonically Computable Real Numbers
Robert Rettinger, Xizhong Zheng
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
Albert Atserias
Lower bounds for on-line single-machine scheduling
Leah Epstein, Rob van Stee
News from the Online Traveling Repairman
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Leen Stougie
Note on Minimal Finite Automata
Galina Jiraskova
On Pseudorandom Generators in NC^0
Mary Cryan, Peter Bro Miltersen
On reducibility and symmetry of disjoint NP-pairs
Pavel Pudlak
On the Approximability of the Steiner Tree Problem
Martin Thimm
On the computational complexity of infinite words
Pavol Duris, Jan Manuch
On the equational definition of the least prefixed point
Luigi Santocanale
On the periods of partial words
Arseny M. Shur, Yulia V. Konovalova
On-line Scheduling with Tight Deadlines
Chiu-Yuen Koo, Tak-Wah Lam, Tsuen-Wan Ngan, Kar-Keung To
Partial Information and Special Case Algorithms
Arfst Nickelsen
Quantifier rank for parity of embedded finite models.
Herve Fournier
Randomness and Reducibility
Rod G. Downey, Denis R. Hirschfeldt, Geoff LaForte
Rational graphs trace context-sensitive languages
Christophe Morvan, Colin Stirling
Refined Search Tree Techniques for the Planar Dominating Set Problem
Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Fran Rosamond, Ulrike Stege
Satisfiability of Systems of Equations over Finite Monoids
Cris Moore, Pascal Tesson, Denis Thérien
Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the MAX Improvement Ratio
Giovanni Di Crescenzo
Space Hierarchy Theorem Revised
Viliam Geffert
Synchronizing finite automata on Eulerian digraphs
Jarkko Kari
Syntactic Semiring of a Language
Libor Polak
The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs
Mitsunori Ogihara, Seinosuke Toda
The Complexity of the Minimal Polynomial
Than Minh Hoang, Thomas Thierauf
The Computational Power of a Family of Decision Forests
Kazuyuki Amano, Tsukuru Hirosawa, Yusuke Watanabe, Akira Maruoka
The Size of Power Automata
Klaus Sutner
The complexity of tensor circuit evaluation
Martin Beaudry, Markus Holzer
The k-Median Problem for Directed Trees
Marek Chrobak, Lawrence Larmore, Wojciech Rytter
There are no sparse NPw-hard sets
Felipe Cucker, Dimitri Grigoriev
Towards regular languages over infinite alphabets
Frank Neven, Thomas Schwentick, Victor Vianu
Upper Bounds on the Bisection Width of 3- and 4-regular Graphs
Burkhard Monien, Robert Preis
Variations on a Theme of Fine and Wilf
Filippo Mignosi, Jeffrey Shallit, Ming-wei Wang
Word Problems for 2-Homogeneous Monoids and Symmetric Logspace
Markus Lohrey


Last changed May 14, 2001.