26. MFCS 2001: Marianske Lazne, Czech Republic

@proceedings{DBLP:conf/mfcs/2001,
  editor    = {Jiri Sgall and
               Ales Pultr and
               Petr Kolman},
  title     = {Mathematical Foundations of Computer Science 2001, 26th International
               Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August
               27-31, 2001, Proceedings},
  booktitle = {MFCS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2136},
  year      = {2001},
  isbn      = {3-540-42496-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talks

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

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