STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings (Lecture Notes in Computer Science)

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006, held in Marseille, France, 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, logic in computer science, as well as current challenges like biological computing, quantum computing, and mobile and net computing. Front Matter....Pages - The Ubiquitous Digital Tree....Pages 1-22 Flat Holonomies on Automata Networks....Pages 23-49 Interprocedurally Analyzing Polynomial Identities....Pages 50-67 External String Sorting: Faster and Cache-Oblivious....Pages 68-79 Amortized Rigidness in Dynamic Cartesian Trees....Pages 80-91 Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes....Pages 92-103 On Critical Exponents in Fixed Points of Binary k -Uniform Morphisms....Pages 104-114 Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms....Pages 115-126 Complete Codes in a Sofic Shift....Pages 127-136 Kolmogorov Complexity with Error....Pages 137-148 Kolmogorov Complexity and the Recursion Theorem....Pages 149-161 Entanglement in Interactive Proof Systems with Binary Answers....Pages 162-171 Quantum Algorithms for Matching and Network Flows....Pages 172-183 The Number of Runs in a String: Improved Analysis of the Linear Upper Bound....Pages 184-195 Estimating Entropy and Entropy Norm on Data Streams....Pages 196-205 Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems....Pages 206-217 Exact Price of Anarchy for Polynomial Congestion Games....Pages 218-229 Oblivious Symmetric Alternation....Pages 230-241 Combining Multiple Heuristics....Pages 242-253 Conflict-Free Colorings of Rectangles Ranges....Pages 254-263 Grid Vertex-Unfolding Orthogonal Polyhedra....Pages 264-276 Theory and Application of Width Bounded Geometric Separator....Pages 277-288 Invariants of Automatic Presentations and Semi-synchronous Transductions....Pages 289-300 On the Accepting Power of 2-Tape Büchi Automata....Pages 301-312 Weighted Picture Automata and Weighted Logics....Pages 313-324 Markov Decision Processes with Multiple Objectives....Pages 325-336 The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms....Pages 337-348 Convergence and Approximation in Potential Games....Pages 349-360 Fast FPT-Algorithms for Cleaning Grids....Pages 361-371 Tradeoffs in Depth-Two Superconcentrators....Pages 372-383 On Hypergraph and Graph Isomorphism with Bounded Color Classes....Pages 384-395 Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences....Pages 396-407 Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets....Pages 408-419 Regularity Problems for Visibly Pushdown Languages....Pages 420-431 Regular Expressions and NFAs Without ε -Transitions....Pages 432-443 Redundancy in Complete Sets....Pages 444-454 Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds....Pages 455-468 Linear Advice for Randomized Logarithmic Space....Pages 469-476 Nested Pebbles and Transitive Closure....Pages 477-488 Definability of Languages by Generalized First-Order Formulas over ( N ,+)....Pages 489-499 Generalized Modal Satisfiability....Pages 500-511 Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games....Pages 512-523 DAG-Width and Parity Games....Pages 524-536 Reliable Computations Based on Locally Decodable Codes....Pages 537-548 Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements....Pages 549-560 A Faster Algorithm for the Steiner Tree Problem....Pages 561-570 Generating Randomized Roundings with Cardinality Constraints and Derandomizations....Pages 571-583 Online Sorting Buffers on Line....Pages 584-595 Optimal Node Routing....Pages 596-607 Memoryless Facility Location in One Pass....Pages 608-620 Energy-Efficient Algorithms for Flow Time Minimization....Pages 621-633 Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games....Pages 634-645 Datalog and Constraint Satisfaction with Infinite Templates....Pages 646-659 Evaluating Monotone Circuits on Cylinders, Planes and Tori....Pages 660-671 Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two....Pages 672-683 Weighted Asynchronous Cellular Automata....Pages 684-695 On the Complexity of the “Most General” Firing Squad Synchronization Problem....Pages 696-711 Back Matter....Pages - 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.