STACS 2006

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, held in February 2006. The 54 revised full papers presented together with three invited papers were carefully reviewed and selected from 283 submissions. The papers address the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, semantics, and logic in computer science.

Inhalt

The Ubiquitous Digital Tree.- Flat Holonomies on Automata Networks.- Interprocedurally Analyzing Polynomial Identities.- External String Sorting: Faster and Cache-Oblivious.- Amortized Rigidness in Dynamic Cartesian Trees.- Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes.- On Critical Exponents in Fixed Points of Binary k-Uniform Morphisms.- Equivalence of -Algebras and Cubic Forms.- Complete Codes in a Sofic Shift.- Kolmogorov Complexity with Error.- Kolmogorov Complexity and the Recursion Theorem.- Entanglement in Interactive Proof Systems with Binary Answers.- Quantum Algorithms for Matching and Network Flows.- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound.- Estimating Entropy and Entropy Norm on Data Streams.- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems.- Exact Price of Anarchy for Polynomial Congestion Games.- Oblivious Symmetric Alternation.- Combining Multiple Heuristics.- Conflict-Free Colorings of Rectangles Ranges.- Grid Vertex-Unfolding Orthogonal Polyhedra.- Theory and Application of Width Bounded Geometric Separator.- Invariants of Automatic Presentations and Semi-synchronous Transductions.- On the Accepting Power of 2-Tape Büchi Automata.- Weighted Picture Automata and Weighted Logics.- Markov Decision Processes with Multiple Objectives.- The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms.- Convergence and Approximation in Potential Games.- Fast FPT-Algorithms for Cleaning Grids.- Tradeoffs in Depth-Two Superconcentrators.- On Hypergraph and Graph Isomorphism with Bounded Color Classes.- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences.- Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.- Regularity Problems for Visibly Pushdown Languages.- Regular Expressions and NFAs Without ?-Transitions.- Redundancy in Complete Sets.- Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds.- Linear Advice for Randomized Logarithmic Space.- Nested Pebbles and Transitive Closure.- Definability of Languages by Generalized First-Order Formulas over (N,+).- Generalized Modal Satisfiability.- Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.- DAG-Width and Parity Games.- Reliable Computations Based on Locally Decodable Codes.- Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements.- A Faster Algorithm for the Steiner Tree Problem.- Generating Randomized Roundings with Cardinality Constraints and Derandomizations.- Online Sorting Buffers on Line.- Optimal Node Routing.- Memoryless Facility Location in One Pass.- Energy-Efficient Algorithms for Flow Time Minimization.- Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.- Datalog and Constraint Satisfaction with Infinite Templates.- Evaluating Monotone Circuits on Cylinders, Planes and Tori.- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two.- Weighted Asynchronous Cellular Automata.- On the Complexity of the "Most General" Firing Squad Synchronization Problem.