34. MFCS 2009: Novy Smokovec, High Tatras, Slovakia

Invited Papers

• Albert Atserias:
  Four Subareas of the Theory of Constraints, and Their Links. 1
  
• Didier Caucal:
  Synchronization of Regular Automata. 2-23
  
• Javier Esparza:
  Stochastic Process Creation. 24-33
  
• Krishnendu Chatterjee, Thomas A. Henzinger, Florian Horn:
  Stochastic Games with Finitary Objectives. 34-54
  
• S. Muthukrishnan:
  Stochastic Data Streams. 55
  
• Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis:
  Recent Advances in Population Protocols. 56-76
  
• Peter Widmayer:
  How to Sort a Train. 77
  

Contributed Papers

• Vikraman Arvind, Pushkar S. Joglekar:
  Arithmetic Circuits, Monomial Algebras and Finite Automata. 78-89
  
• Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, Maria Kyropoulou:
  An Improved Approximation Bound for Spanning Star Forest and Color Saving. 90-101
  
• Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou:
  Energy-Efficient Communication in Multi-interface Wireless Networks. 102-111
  
• Vincenzo Auletta, Paolo Penna, Giuseppe Persiano:
  Private Capacities in Mechanism Design. 112-123
  
• Nadja Betzler, Britta Dorn:
  Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules. 124-136
  
• Ivona Bezáková, William A. Rummler:
  Sampling Edge Covers in 3-Regular Graphs. 137-148
  
• Alessandro Bianco, Marco Faella, Fabio Mogavero, Aniello Murano:
  Balanced Paths in Colored Graphs. 149-161
  
• Bernd Borchert, Pierre McKenzie, Klaus Reinhardt:
  Few Product Gates But Many Zeros. 162-174
  
• Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
  Branching Programs for Tree Evaluation. 175-186
  
• Irénée Briquel, Pascal Koiran:
  A Dichotomy Theorem for Polynomial Evaluation. 187-198
  
• Yi Cao, Joseph C. Culberson, Lorna Stewart:
  DP-Complete Problems Derived from Extremal NP-Complete Properties. 199-210
  
• Arturo Carpi, Flavio D'Alessandro:
  The Synchronization Problem for Locally Strongly Transitive Automata. 211-222
  
• Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca:
  Constructing Brambles. 223-234
  
• Francisco Claude, Gonzalo Navarro:
  Self-indexed Text Compression Using Straight-Line Programs. 235-246
  
• Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci:
  Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants. 247-257
  
• Anuj Dawar, Yuguo He:
  Parameterized Complexity Classes under Logical Reductions. 258-269
  
• Julien Degorre, Marc Kaplan, Sophie Laplante, Jérémie Roland:
  The Communication Complexity of Non-signaling Distributions. 270-281
  
• Feodor F. Dragan, Yang Xiang:
  How to Use Spanning Trees to Navigate in Graphs. 282-294
  
• Sagarmoy Dutta, Piyush P. Kurur:
  Representing Groups on Graphs. 295-306
  
• Marco Faella:
  Admissible Strategies in Infinite Games over Graphs. 307-318
  
• Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier:
  A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. 319-330
  
• Diego Figueira, Luc Segoufin:
  Future-Looking Logics on Data Words and Trees. 331-343
  
• Marco Gaboardi, Luca Roversi, Luca Vercelli:
  A By-Level Analysis of Multiplicative Exponential Linear Logic. 344-355
  
• Pawel Gawrychowski, Artur Jez:
  Hyper-minimisation Made Efficient. 356-368
  
• Wouter Gelade, Marc Gyssens, Wim Martens:
  Regular Expressions with Counting: Weak versus Strong Determinism. 369-381
  
• Petr A. Golovach, Pinar Heggernes:
  Choosability of P5-Free Graphs. 382-391
  
• Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle:
  Time-Bounded Kolmogorov Complexity and Solovay Functions. 392-402
  
• Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos:
  The Longest Path Problem Is Polynomial on Interval Graphs. 403-414
  
• Lukasz Kaiser:
  Synthesis for Structure Rewriting Systems. 415-426
  
• Ahmet Kara, Volker Weber, Martin Lange, Thomas Schwentick:
  On the Hybrid Extension of CTL and CTL⁺. 427-438
  
• Jarkko Kari, Pascal Vanier, Thomas Zeume:
  Bounds on Non-surjective Cellular Automata. 439-450
  
• Alexander Kartzow:
  FO Model Checking on Nested Pushdown Trees. 451-463
  
• Delia Kesner, Fabien Renaud:
  The Prismoid of Resources. 464-476
  
• Bakhadyr Khoussainov, Jiamou Liu, Imran Khaliq:
  A Dynamic Algorithm for Reachability Games Played on Trees. 477-488
  
• Daniel Kirsten:
  An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable. 489-500
  
• Adrian Kosowski, Alfredo Navarra:
  Graph Decomposition for Improving Memoryless Periodic Exploration. 501-512
  
• Manfred Kufleitner, Pascal Weil:
  On FO2 Quantifier Alternation over Words. 513-524
  
• Tomi Kärki, Anne Lacroix, Michel Rigo:
  On the Recognizability of Self-generating Sets. 525-536
  
• Johannes Köbler, Sebastian Kuhnert:
  The Isomorphism Problem for k-Trees Is Complete for Logspace. 537-548
  
• Violetta Lonati, Matteo Pradella:
  Snake-Deterministic Tiling Systems. 549-560
  
• P. Madhusudan, Mahesh Viswanathan:
  Query Automata for Nested Words. 561-573
  
• Giulio Manzonetto:
  A General Class of Models of . 574-586
  
• Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss:
  The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I. 587-599
  
• Sotiris E. Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis:
  Colouring Non-sparse Random Intersection Graphs. 600-611
  
• Periklis A. Papakonstantinou:
  On the Structure of Optimal Greedy Computation (for Job Scheduling). 612-623
  
• Kai Plociennik:
  A Probabilistic PTAS for Shortest Common Superstring. 624-635
  
• Ezra Resnick, Yoram Bachrach, Reshef Meir, Jeffrey S. Rosenschein:
  The Cost of Stability in Network Flow Games. 636-650
  
• Gaétan Richard:
  (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata. 651-662
  
• Martin Rötteler:
  Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm. 663-674
  
• Sven Schewe:
  From Parity and Payoff Games to Linear Programming. 675-686
  
• Kohtaro Tadaki:
  Partial Randomness and Dimension of Recursively Enumerable Reals. 687-699
  
• Tadao Takaoka:
  Partial Solution and Entropy. 700-711
  
• Tony Tan:
  On Pebble Automata for Data Languages with Decidable Emptiness Problem. 712-723
  
• Kei Uchizawa, Takao Nishizeki, Eiji Takimoto:
  Size and Energy of Threshold Circuits Computing Mod Functions. 724-735
  
• Robert Rettinger, Xizhong Zheng:
  Points on Computable Curves of Computable Lengths. 736-743
  
• Stanislav Zivný, David A. Cohen, Peter G. Jeavons:
  The Expressive Power of Binary Submodular Functions. 744-757