MFCS 2001

26th International Symposium on
Mathematical Foundations of Computer Science

August 27 - 31, 2001
Marianske Lazne, Czech Republic
MFCS

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
 

Homepage: http://www.math.cas.cz/~mfcs2001/

Last changed May 14, 2001.