Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001 Mariánské Lázne, Czech Republic, August 27–31, 2001 Proceedings

Dana S. Scott (auth.), Jiří Sgall, Aleš Pultr, Petr Kolman (eds.)3540424962, 9783540424963

This book constitutes the refereed proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001, held in Marianske Lazne, Czech Republic in August 2001. The 51 revised full papers presented together with 10 invited contributions were carefully reviewed and selected from a total of 118 submissions. All current aspects of theoretical computer science are addressed ranging from mathematical logic and programming theory to algorithms, discrete mathematics, and complexity theory. Besides classical issues, modern topics like quantum computing are discussed as well.

---

Table of contents :
A New Category for Semantics….Pages 1-2
On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity….Pages 3-17
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory….Pages 18-33
Some Recent Results on Data Mining and Search….Pages 33-36
Hypertree Decompositions: A Survey….Pages 37-57
The Strength of Non-size-increasing Computation (Introduction and Summary)….Pages 58-61
Introduction to Recent Quantum Algorithms….Pages 62-74
Decomposition Methods and Sampling Circuits in the Cartesian Lattice….Pages 74-86
New Algorithms for k -SAT Based on the Local Search Principle….Pages 87-95
Linear Temporal Logic and Finite Semigroups….Pages 96-110
Refined Search Tree Technique for Dominating Set on Planar Graphs….Pages 111-123
The Computational Power of a Family of Decision Forests….Pages 123-134
Exact Results for Accepting Probabilities of Quantum Automata….Pages 135-147
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms….Pages 148-158
Analysis Problems for Sequential Dynamical Systems and Communicating State Machines….Pages 159-172
The Complexity of Tensor Circuit Evaluation….Pages 173-185
Computing Reciprocals of Bivariate Power Series….Pages 186-197
Automatic Verification of Recursive Procedures with One Integer Parameter….Pages 198-211
Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds….Pages 212-223
Computable Versions of Baire’s Category Theorem….Pages 224-235
Automata on Linear Orderings….Pages 236-247
Algorithmic Information Theory and Cellular Automata Dynamics….Pages 248-260
The k -Median Problem for Directed Trees….Pages 260-271
On Pseudorandom Generators in NC 0 ….Pages 272-284
There Are No Sparse NP w -Hard Sets….Pages 285-291
Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the Max Improvement Ratio….Pages 292-304
(H,C,K) -Coloring: Fast, Easy, and Hard Cases….Pages 304-315
Randomness and Reductibility….Pages 316-327
On the Computational Complexity of Infinite Words….Pages 328-337
Lower Bounds for On-Line Single-Machine Scheduling….Pages 338-350
Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings….Pages 351-362
A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing….Pages 363-374
Quantifier Rank for Parity of Embedded Finite Models….Pages 375-386
Space Hierarchy Theorem Revised….Pages 387-397
Converting Two—Way Nondeterministic Unary Automata into Simpler Automata….Pages 398-407
The Complexity of the Minimal Polynomial….Pages 408-420
Note on Minimal Finite Automata….Pages 421-431
Synchronizing Finite Automata on Eulerian Digraphs….Pages 432-438
A Time Hierarchy for Bounded One-Way Cellular Automata….Pages 439-450
Checking Amalgamability Conditions for Casl Architectural Specifications….Pages 451-463
On-Line Scheduling with Tight Deadlines….Pages 464-473
Complexity Note on Mixed Hypergraphs….Pages 474-485
News from the Online Traveling Repairman….Pages 487-499
Word Problems for 2-Homogeneous Monoids and Symmetric Logspace….Pages 500-512
Variations on a Theorem of Fine & Wilf….Pages 512-523
Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs….Pages 524-536
Satisfiability of Systems of Equations over Finite Monoids….Pages 537-547
Rational Graphs Trace Context-Sensitive Languages….Pages 548-559
Towards Regular Languages over Infinite Alphabets….Pages 560-572
Partial Information and Special Case Algorithms….Pages 573-584
The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs….Pages 585-597
From Bidirectionality to Alternation….Pages 598-610
Syntactic Semiring of a Language….Pages 611-620
On Reducibility and Symmetry of Disjoint NP-Pairs….Pages 621-632
Hierarchy of Monotonically Computable Real Numbers….Pages 633-644
On the Equational Definition of the Least Prefixed Point….Pages 645-656
On the Periods of Partial Words….Pages 657-665
The Size of Power Automata….Pages 666-677
On the Approximability of the Steiner Tree Problem….Pages 678-689
Alignment between Two RNA Structures….Pages 690-703
Characterization of Context-Free Languages with Polynomially Bounded Ambiguity….Pages 703-714