STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings

Serge Abiteboul (auth.), Wolfgang Thomas, Pascal Weil (eds.)3540709177, 9783540709176

This book constitutes the refereed proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007, held in Aachen, Germany in February 2007.

The 56 revised full papers presented together with 3 invited papers were carefully reviewed and selected from about 400 submissions. The papers address the whole range of theoretical computer science including algorithms and data structures, automata and formal languages, complexity theory, logic in computer science, semantics, specification, and verification of programs, rewriting and deduction, as well as current challenges like biological computing, quantum computing, and mobile and net computing.

---

Table of contents :
Front Matter….Pages –
A Calculus and Algebra for Distributed Data Management….Pages 1-11
The Büchi Complementation Saga….Pages 12-22
Speed-Up Techniques for Shortest-Path Computations….Pages 23-36
Compact Forbidden-Set Routing….Pages 37-48
A New Bound for Pure Greedy Hot Potato Routing….Pages 49-60
Wavelength Management in WDM Rings to Maximize the Number of Connections….Pages 61-72
A First Investigation of Sturmian Trees….Pages 73-84
On the Size of the Universal Automaton of a Regular Language….Pages 85-96
Correlations of Partial Words….Pages 97-108
Testing Convexity Properties of Tree Colorings….Pages 109-120
Why Almost All k -Colorable Graphs Are Easy….Pages 121-132
On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds….Pages 133-144
A New Rank Technique for Formula Size Lower Bounds….Pages 145-156
Hard Metrics from Cayley Graphs of Abelian Groups….Pages 157-162
Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs….Pages 163-174
Light Orthogonal Networks with Constant Geometric Dilation….Pages 175-187
Admissibility in Infinite Games….Pages 188-199
Pure Stationary Optimal Strategies in Markov Decision Processes….Pages 200-211
Symmetries and the Complexity of Pure Nash Equilibrium….Pages 212-223
Computing Representations of Matroids of Bounded Branch-Width….Pages 224-235
Characterizing Minimal Interval Completions….Pages 236-247
The Complexity of Unions of Disjoint Sets….Pages 248-259
Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity….Pages 260-271
Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets….Pages 272-283
On the Complexity of Affine Image Matching….Pages 284-295
On Fixed Point Equations over Commutative Semirings….Pages 296-307
An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings….Pages 308-319
A Cubic Kernel for Feedback Vertex Set….Pages 320-331
The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting….Pages 332-343
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs….Pages 344-355
A Search Algorithm for the Maximal Attractor of a Cellular Automaton….Pages 356-366
Universal Tilings….Pages 367-380
On the Complexity of Unary Tiling-Recognizable Picture Languages….Pages 381-392
A Characterization of Strong Learnability in the Statistical Query Model….Pages 393-404
On the Consistency of Discrete Bayesian Learning….Pages 405-416
VPSPACE and a Transfer Theorem over the Reals….Pages 417-428
On Symmetric Signatures in Holographic Algorithms….Pages 429-440
Randomly Rounding Rationals with Cardinality Constraints and Derandomizations….Pages 441-452
Cheating to Get Better Roommates in a Random Stable Matching….Pages 453-464
A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window….Pages 465-476
Arithmetizing Classes Around NC 1 and L ….Pages 477-488
The Polynomially Bounded Perfect Matching Problem Is in NC 2 ….Pages 489-499
Languages with Bounded Multiparty Communication Complexity….Pages 500-511
New Approximation Algorithms for Minimum Cycle Bases of Graphs….Pages 512-523
On Completing Latin Squares….Pages 524-535
Small Space Representations for Metric Min-Sum k -Clustering and Their Applications….Pages 536-548
An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic….Pages 549-560
Bounded-Variable Fragments of Hybrid Logics….Pages 561-572
Rank-1 Modal Logics Are Coalgebraic….Pages 573-585
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups….Pages 586-597
Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem….Pages 598-609
Quantum Network Coding….Pages 610-621
Reachability in Unions of Commutative Rewriting Systems Is Decidable….Pages 622-633
Associative-Commutative Deducibility Constraints….Pages 634-645
On the Automatic Analysis of Recursive Security Protocols with XOR….Pages 646-657
Improved Online Algorithms for the Sorting Buffer Problem….Pages 658-669
Cost Sharing Methods for Makespan and Completion Time Scheduling….Pages 670-681
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests….Pages 682-693
Enumerating All Solutions for Constraint Satisfaction Problems….Pages 694-705
Back Matter….Pages –