Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings

Front Matter....Pages -
Four Subareas of the Theory of Constraints, and Their Links....Pages 1-1
Synchronization of Regular Automata....Pages 2-23
Stochastic Process Creation....Pages 24-33
Stochastic Games with Finitary Objectives....Pages 34-54
Stochastic Data Streams....Pages 55-55
Recent Advances in Population Protocols....Pages 56-76
How to Sort a Train....Pages 77-77
Arithmetic Circuits, Monomial Algebras and Finite Automata....Pages 78-89
An Improved Approximation Bound for Spanning Star Forest and Color Saving....Pages 90-101
Energy-Efficient Communication in Multi-interface Wireless Networks....Pages 102-111
Private Capacities in Mechanism Design....Pages 112-123
Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules....Pages 124-136
Sampling Edge Covers in 3-Regular Graphs....Pages 137-148
Balanced Paths in Colored Graphs....Pages 149-161
Few Product Gates But Many Zeros....Pages 162-174
Branching Programs for Tree Evaluation....Pages 175-186
A Dichotomy Theorem for Polynomial Evaluation....Pages 187-198
DP-Complete Problems Derived from Extremal NP-Complete Properties....Pages 199-210
The Synchronization Problem for Locally Strongly Transitive Automata....Pages 211-222
Constructing Brambles....Pages 223-234
Self-indexed Text Compression Using Straight-Line Programs....Pages 235-246
Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants....Pages 247-257
Parameterized Complexity Classes under Logical Reductions....Pages 258-269
The Communication Complexity of Non-signaling Distributions....Pages 270-281
How to Use Spanning Trees to Navigate in Graphs....Pages 282-294
Representing Groups on Graphs....Pages 295-306
Admissible Strategies in Infinite Games over Graphs....Pages 307-318
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems....Pages 319-330
Future-Looking Logics on Data Words and Trees....Pages 331-343
A By-Level Analysis of Multiplicative Exponential Linear Logic....Pages 344-355
Hyper-minimisation Made Efficient....Pages 356-368
Regular Expressions with Counting: Weak versus Strong Determinism....Pages 369-381
Choosability of P 5 -Free Graphs....Pages 382-391
Time-Bounded Kolmogorov Complexity and Solovay Functions....Pages 392-402
The Longest Path Problem Is Polynomial on Interval Graphs....Pages 403-414
Synthesis for Structure Rewriting Systems....Pages 415-426
On the Hybrid Extension of CTL and CTL  +  ....Pages 427-438
Bounds on Non-surjective Cellular Automata....Pages 439-450
FO Model Checking on Nested Pushdown Trees....Pages 451-463
The Prismoid of Resources....Pages 464-476
A Dynamic Algorithm for Reachability Games Played on Trees....Pages 477-488
An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable....Pages 489-500
Graph Decomposition for Improving Memoryless Periodic Exploration....Pages 501-512
On FO 2 Quantifier Alternation over Words....Pages 513-524
On the Recognizability of Self-generating Sets....Pages 525-536
The Isomorphism Problem for k -Trees Is Complete for Logspace....Pages 537-548
Snake-Deterministic Tiling Systems....Pages 549-560
Query Automata for Nested Words....Pages 561-573
A General Class of Models of $\mathcal{H}^*$ ....Pages 574-586
The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I....Pages 587-599
Colouring Non-sparse Random Intersection Graphs....Pages 600-611
On the Structure of Optimal Greedy Computation (for Job Scheduling)....Pages 612-623
A Probabilistic PTAS for Shortest Common Superstring....Pages 624-635
The Cost of Stability in Network Flow Games....Pages 636-650
(Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata....Pages 651-662
Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm....Pages 663-674
From Parity and Payoff Games to Linear Programming....Pages 675-686
Partial Randomness and Dimension of Recursively Enumerable Reals....Pages 687-699
Partial Solution and Entropy....Pages 700-711
On Pebble Automata for Data Languages with Decidable Emptiness Problem....Pages 712-723
Size and Energy of Threshold Circuits Computing Mod Functions....Pages 724-735
Points on Computable Curves of Computable Lengths....Pages 736-743
The Expressive Power of Binary Submodular Functions....Pages 744-757
Back Matter....Pages -