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

Cover Page......Page 1
Lecture Notes in Computer Science 5734......Page 2
Title Page......Page 3
ISBN 3642038158......Page 4
Preface......Page 5
Conference Organization......Page 6
Table of Contents......Page 10
Four Subareas of the Theory of Constraints, and Their Links......Page 15
Synchronization of Regular Automata......Page 16
The Complexity of Recognising Expressible Functions......Page 0
References......Page 37
Stochastic Process Creation......Page 38
References......Page 47
Stochastic Games with Finitary Objectives......Page 48
References......Page 67
Stochastic Data Streams......Page 69
Recent Advances in Population Protocols......Page 70
References......Page 89
How to Sort a Train......Page 91
Arithmetic Circuits, Monomial Algebras and Finite Automata......Page 92
References......Page 103
An Improved Approximation Bound for Spanning Star Forest and Color Saving......Page 104
References......Page 114
Energy-Efficient Communication in Multi-interface Wireless Networks......Page 116
References......Page 124
Private Capacities in Mechanism Design......Page 126
References......Page 137
Towards a Dichotomy of Finding PossibleWinners in Elections Based on Scoring Rules......Page 138
Scoring Rules of the Form ($\\alpha_{1}$, $\\alpha_{2}$,...,0)......Page 148
References......Page 149
Sampling Edge Covers in 3-Regular Graphs......Page 151
References......Page 162
Balanced Paths in Colored Graphs......Page 163
References......Page 174
Few Product Gates But Many Zeros......Page 176
References......Page 187
Branching Programs for Tree Evaluation......Page 189
The Ne\\v{c}iporuk Method......Page 194
References......Page 199
A Dichotomy Theorem for Polynomial Evaluation......Page 201
References......Page 212
DP-Complete Problems Derived from Extremal NP-Complete Properties......Page 213
References......Page 223
The Synchronization Problem for Locally Strongly Transitive Automata......Page 225
References......Page 235
Constructing Brambles......Page 237
References......Page 247
Self-indexed Text Compression Using Straight-Line Programs......Page 249
References......Page 259
Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants......Page 261
References......Page 270
Parameterized Complexity Classes under Logical Reductions......Page 272
References......Page 283
The Communication Complexity of Non-signaling Distributions......Page 284
References......Page 294
How to Use Spanning Trees to Navigate in Graphs......Page 296
References......Page 306
Representing Groups on Graphs......Page 309
References......Page 320
Admissible Strategies in Infinite Games over Graphs......Page 321
References......Page 332
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems......Page 333
References......Page 344
Future-Looking Logics on Data Words and Trees......Page 345
References......Page 356
A By-Level Analysis of Multiplicative Exponential Linear Logic......Page 358
References......Page 368
Hyper-minimisation Made Efficient......Page 370
References......Page 381
Regular Expressions with Counting: Weak versus Strong Determinism......Page 383
References......Page 394
Choosability of $P_{5}$-Free Graphs......Page 396
References......Page 404
Time-Bounded Kolmogorov Complexity and Solovay Functions......Page 406
References......Page 415
The Longest Path Problem Is Polynomial on Interval Graphs......Page 417
References......Page 427
Synthesis for Structure Rewriting Systems......Page 429
References......Page 440
On the Hybrid Extension of CTL and CTL$^{+}$......Page 441
References......Page 451
Bounds on Non-surjective Cellular Automata......Page 453
References......Page 463
FO Model Checking on Nested Pushdown Trees......Page 465
References......Page 477
The Prismoid of Resources......Page 478
References......Page 489
A Dynamic Algorithm for Reachability Games Played on Trees......Page 491
References......Page 502
An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable......Page 503
References......Page 514
Graph Decomposition for Improving Memoryless Periodic Exploration......Page 515
References......Page 526
On FO^2 Quantifier Alternation over Words......Page 527
References......Page 538
On the Recognizability of Self-generating Sets......Page 539
References......Page 550
The Isomorphism Problem for $k$-Trees Is Complete for Logspace......Page 551
References......Page 561
Snake-Deterministic Tiling Systems......Page 563
References......Page 574
Query Automata for Nested Words......Page 575
References......Page 586
A General Class of Models of ${\\mathcal H*}......Page 588
References......Page 599
The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I......Page 601
References......Page 611
Colouring Non-sparse Random Intersection Graphs......Page 614
References......Page 623
On the Structure of Optimal Greedy Computation (for Job Scheduling)......Page 626
References......Page 637
A Probabilistic PTAS for Shortest Common Superstring......Page 638
References......Page 649
The Cost of Stability in Network Flow Games......Page 650
References......Page 663
(Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata......Page 665
References......Page 676
Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm......Page 677
References......Page 687
From Parity and Payoff Games to Linear Programming......Page 689
References......Page 699
Partial Randomness and Dimension of Recursively Enumerable Reals......Page 701
References......Page 712
Partial Solution and Entropy......Page 714
References......Page 725
On Pebble Automata for Data Languages with Decidable Emptiness Problem......Page 726
References......Page 737
Size and Energy of Threshold Circuits Computing Mod Functions......Page 738
References......Page 748
Points on Computable Curves of Computable Lengths......Page 750
References......Page 757
The Expressive Power of Binary Submodular Functions......Page 758
References......Page 770
Author Index......Page 772