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

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