STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, ProceedingsThis 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. |
Contents
The Ubiquitous Digital Tree | 1 |
Flat Holonomies on Automata Networks | 23 |
Interprocedurally Analyzing Polynomial Identities | 50 |
Faster and CacheOblivious | 68 |
DistributionSensitive Construction of MinimumRedundancy Prefix | 92 |
Equivalence of FAlgebras and Cubic Forms | 115 |
Kolmogorov Complexity with Error | 137 |
Entanglement in Interactive Proof Systems with Binary Answers | 162 |
Winnow Yields | 408 |
Regular Expressions and NFAs Without εTransitions | 432 |
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds | 455 |
Linear Advice for Randomized Logarithmic Space | 469 |
Definability of Languages by Generalized FirstOrder Formulas over | 489 |
Strategy Improvement and Randomized Subexponential Algorithms | 512 |
Reliable Computations Based on Locally Decodable Codes | 537 |
A Faster Algorithm for the Steiner Tree Problem | 561 |
Improved Analysis of the Linear | 184 |
Improved Approximation Algorithms | 206 |
Oblivious Symmetric Alternation | 230 |
ConflictFree Colorings of Rectangles Ranges | 254 |
Theory and Application of Width Bounded Geometric Separator | 277 |
On the Accepting Power of 2Tape Buchi Automata | 301 |
Markov Decision Processes with Multiple Objectives | 325 |
The Algorithmic Structure of Group Strategyproof BudgetBalanced | 337 |
Fast FPTAlgorithms for Cleaning Grids | 361 |
On Hypergraph and Graph Isomorphism with Bounded Color Classes | 384 |
Online Sorting Buffers on Line | 584 |
Memoryless Facility Location in One Pass | 608 |
EnergyEfficient Algorithms for Flow Time Minimization | 621 |
Efficient Qualitative Analysis of Classes of Recursive Markov Decision | 634 |
Datalog and Constraint Satisfaction with Infinite Templates | 646 |
Evaluating Monotone Circuits on Cylinders Planes and Tori | 660 |
Weighted Asynchronous Cellular Automata | 684 |
Author Index | 713 |
Other editions - View all
Common terms and phrases
accepted algorithm allows apply approximation assignment assume automata binary bits bound called circuits color complexity Computer condition connected consider constant constraint construction contains corresponding cost define defined definition denote deterministic directed distance edges elements equal equivalent example exists facility fact finite first formula function give given graph Hence holds implies improved initial input instance interval known label languages least Lemma length linear logic lower mapping maximal node Note obtain operations optimal output path player polynomial positive present probability problem proof Proposition prove random recursive reduction regular relation requires respectively result robots root rounding runs schedule Science sequence single solution space step strategy strings structure Theorem Theory transition tree variables vertex vertices weights