Mathematical Foundations of Computer Science 2001

Invited Talks.- A New Category for Semantics.- On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity.- Playing Games with Algorithms: Algorithmic Combinatorial Game Theory.- Some Recent Results on Data Mining and Search.- Hypertree Decompositions: A Survey.- The Strength of Non-size-increasing Computation (Introduction and Summary).- to Recent Quantum Algorithms.- Decomposition Methods and Sampling Circuits in the Cartesian Lattice.- New Algorithms for k-SAT Based on the Local Search Principle.- Linear Temporal Logic and Finite Semigroups.- Contributed Talks.- Refined Search Tree Technique for Dominating Set on Planar Graphs.- The Computational Power of a Family of Decision Forests.- Exact Results for Accepting Probabilities of Quantum Automata.- Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms.- Analysis Problems for Sequential Dynamical Systems and Communicating State Machines.- The Complexity of Tensor Circuit Evaluation.- Computing Reciprocals of Bivariate Power Series.- Automatic Verification of Recursive Procedures with One Integer Parameter.- Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds.- Computable Versions of Baire’s Category Theorem.- Automata on Linear Orderings.- Algorithmic Information Theory and Cellular Automata Dynamics.- The k-Median Problem for Directed Trees.- On Pseudorandom Generators in NC0.- There Are No Sparse NPw-Hard Sets.- Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the Max Improvement Ratio.- (H,C,K) -Coloring: Fast, Easy, and Hard Cases.- Randomness and Reductibility.- On the Computational Complexity of Infinite Words.- Lower Bounds for On-Line Single-Machine Scheduling.- Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings.- A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing.- Quantifier Rank for Parity of Embedded Finite Models.- Space Hierarchy Theorem Revised.- Converting Two—Way Nondeterministic Unary Automata into Simpler Automata.- The Complexity of the Minimal Polynomial.- Note on Minimal Finite Automata.- Synchronizing Finite Automata on Eulerian Digraphs.- A Time Hierarchy for Bounded One-Way Cellular Automata.- Checking Amalgamability Conditions forCasl Architectural Specifications.- On-Line Scheduling with Tight Deadlines.- Complexity Note on Mixed Hypergraphs.- News from the Online Traveling Repairman.- Word Problems for 2-Homogeneous Monoids and Symmetric Logspace.- Variations on a Theorem of Fine & Wilf.- Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs.- Satisfiability of Systems of Equations over Finite Monoids.- Rational Graphs Trace Context-Sensitive Languages.- Towards Regular Languages over Infinite Alphabets.- Partial Information and Special Case Algorithms.- The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs.- From Bidirectionality to Alternation.- Syntactic Semiring of a Language.- On Reducibility and Symmetry of Disjoint NP-Pairs.- Hierarchy of Monotonically Computable Real Numbers.- On the Equational Definition of the Least Prefixed Point.- On the Periods of Partial Words.- The Size of Power Automata.- On the Approximability of the Steiner Tree Problem.- Alignment between Two RNA Structures.- Characterization of Context-Free Languages with Polynomially Bounded Ambiguity.