26. MFCS 2001: Marianske Lazne, Czech Republic

Invited Talks

• Dana S. Scott:
  A New Category for Semantics. 1-2
  
• Peter Bürgisser:
  On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity. 3-17
  
• Erik D. Demaine:
  Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. 18-32
  
• Amos Fiat:
  Some Recent Results on Data Mining and Search. 33-36
  
• Georg Gottlob, Nicola Leone, Francesco Scarcello:
  Hypertree Decompositions: A Survey. 37-57
  
• Martin Hofmann:
  The Strength of Non-size-increasing Computation (Introduction and Summary). 58-61
  
• Peter Høyer:
  Introduction to Recent Quantum Algorithms. 62-73
  
• Dana Randall:
  Decomposition Methods and Sampling Circuits in the Cartesian Lattice. 74-86
  
• Uwe Schöning:
  New Algorithms for k -SAT Based on the Local Search Principle. 87-95
  
• Thomas Wilke:
  Linear Temporal Logic and Finite Semigroups. 96-110
  

Contributed Talks

• Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Frances A. Rosamond, Ulrike Stege:
  Refined Search Tree Technique for DOMINATING SET on Planar Graphs. 111-122
  
• Kazuyuki Amano, Tsukuru Hirosawa, Yusuke Watanabe, Akira Maruoka:
  The Computational Power of a Family of Decision Forests. 123-134
  
• Andris Ambainis, Arnolds Kikusts:
  Exact Results for Accepting Probabilities of Quantum Automata. 135-147
  
• Albert Atserias:
  Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms. 148-158
  
• Christopher L. Barrett, Harry B. Hunt III, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns:
  Analysis Problems for Sequential Dynamical Systems and Communicating State Machines. 159-172
  
• Martin Beaudry, Markus Holzer:
  The Complexity of Tensor Circuit Evaluation. 173-185
  
• Markus Bläser:
  Computing Reciprocals of Bivariate Power Series. 186-197
  
• Ahmed Bouajjani, Peter Habermehl, Richard Mayr:
  Automatic Verification of Recursive Procedures with One Integer Parameter. 198-211
  
• Henrik Brosenne, Matthias Homeister, Stephan Waack:
  Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds. 212-223
  
• Vasco Brattka:
  Computable Versions of Baire's Category Theorem. 224-235
  
• Véronique Bruyère, Olivier Carton:
  Automata on Linear Orderings. 236-247
  
• Julien Cervelle, Bruno Durand, Enrico Formenti:
  Algorithmic Information Theory and Cellular Automata Dynamics. 248-259
  
• Marek Chrobak, Lawrence L. Larmore, Wojciech Rytter:
  The k-Median Problem for Directed Trees. 260-271
  
• Mary Cryan, Peter Bro Miltersen:
  On Pseudorandom Generators in NC. 272-284
  
• Felipe Cucker, Dima Grigoriev:
  There Are No Sparse NP_W-Hard Sets. 285-291
  
• Giovanni Di Crescenzo:
  Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the Max Improvement Ratio. 292-303
  
• Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
  (H, C, K)-Coloring: Fast, Easy, and Hard Cases. 304-315
  
• Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte:
  Randomness and Reducibility. 316-327
  
• Pavol Duris, Ján Manuch:
  On the Computational Complexity of Infinite Words. 328-337
  
• Leah Epstein, Rob van Stee:
  Lower Bounds for On-Line Single-Machine Scheduling. 338-350
  
• Thomas Erlebach:
  Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings. 351-362
  
• Wolfgang Espelage, Egon Wanke:
  A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing. 363-374
  
• Hervé Fournier:
  Quantifier Rank for Parity of Embedded Finite Models. 375-386
  
• Viliam Geffert:
  Space Hierarchy Theorem Revised. 387-397
  
• Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini:
  Converting Two-Way Nondeterministic Unary Automata into Simpler Automata. 398-407
  
• Thanh Minh Hoang, Thomas Thierauf:
  The Complexity of the Minimal Polynomial. 408-420
  
• Galina Jirásková:
  Note on Minimal Finite Automata. 421-431
  
• Jarkko Kari:
  Synchronizing Finite Automata on Eulerian Digraphs. 432-438
  
• Andreas Klein, Martin Kutrib:
  A Time Hierarchy for Bounded One-Way Cellular Automata. 439-450
  
• Bartek Klin, Piotr Hoffman, Andrzej Tarlecki, Lutz Schröder, Till Mossakowski:
  Checking Amalgamability Conditions for C ASL Architectural Specifications. 451-463
  
• Chiu-Yuen Koo, Tak Wah Lam, Tsuen-Wan Ngan, Kar-Keung To:
  On-Line Scheduling with Tight Deadlines. 464-473
  
• Daniel Král, Jan Kratochvíl, Heinz-Jürgen Voss:
  Complexity Note on Mixed Hypergraphs. 474-486
  
• Sven Oliver Krumke, Willem de Paepe, Diana Poensgen, Leen Stougie:
  News from the Online Traveling Repairman. 487-499
  
• Markus Lohrey:
  Word Problems for 2-Homogeneous Monoids and Symmetric Logspace. 500-511
  
• Filippo Mignosi, Jeffrey Shallit, Ming-wei Wang:
  Variations on a Theorem of Fine & Wilf. 512-523
  
• Burkhard Monien, Robert Preis:
  Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs. 524-536
  
• Cristopher Moore, Pascal Tesson, Denis Thérien:
  Satisfiability of Systems of Equations over Finite Monoids. 537-547
  
• Christophe Morvan, Colin Stirling:
  Rational Graphs Trace Context-Sensitive Languages. 548-559
  
• Frank Neven, Thomas Schwentick, Victor Vianu:
  Towards Regular Languages over Infinite Alphabets. 560-572
  
• Arfst Nickelsen:
  Partial Information and Special Case Algorithms. 573-584
  
• Mitsunori Ogihara, Seinosuke Toda:
  The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs. 585-597
  
• Nir Piterman, Moshe Y. Vardi:
  From Bidirectionality to Alternation. 598-610
  
• Libor Polák:
  Syntactic Semiring of a Language. 611-620
  
• Pavel Pudlák:
  On Reducibility and Symmetry of Disjoint NP-Pairs. 621-632
  
• Robert Rettinger, Xizhong Zheng:
  Hierarchy of Monotonically Computable Real Numbers. 633-644
  
• Luigi Santocanale:
  On the Equational Definition of the Least Prefixed Point. 645-656
  
• Arseny M. Shur, Yulia V. Konovalova:
  On the Periods of Partial Words. 657-665
  
• Klaus Sutner:
  The Size of Power Automata. 666-677
  
• Martin Thimm:
  On the Approximability of the Steiner Tree Problem. 678-689
  
• Zhuozhi Wang, Kaizhong Zhang:
  Alignment between Two RNA Structures. 690-702
  
• Klaus Wich:
  Characterization of Context-Free Languages with Polynomially Bounded Ambiguity. 703-714