Stacs 2006: 23rd Annual Symposium On Theoretical Aspects Of Computer Science, Marseille, France, February 23-25 by Bruno DurandStacs 2006: 23rd Annual Symposium On Theoretical Aspects Of Computer Science, Marseille, France, February 23-25 by Bruno Durand

Stacs 2006: 23rd Annual Symposium On Theoretical Aspects Of Computer Science, Marseille, France…

byBruno DurandEditorWolfgang Thomas

Paperback | February 14, 2006

Pricing and Purchase Info

$204.18 online 
$247.50 list price save 17%
Earn 1,021 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


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.

Title:Stacs 2006: 23rd Annual Symposium On Theoretical Aspects Of Computer Science, Marseille, France…Format:PaperbackDimensions:714 pages, 23.5 × 15.5 × 0.07 inPublished:February 14, 2006Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:3540323015

ISBN - 13:9783540323013


Table of Contents

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.