Automata, Languages and Programming

1. Front Matter

   PDF

2. Track B: Invited Lectures

   1. A Survey of Stochastic Games with Limsup and Liminf Objectives

      • Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger

      Pages 1-15

   2. Tractable Optimization Problems through Hypergraph-Based Structural Restrictions

      • Georg Gottlob, Gianluigi Greco, Francesco Scarcello

      Pages 16-30

3. Track B: Contributed Papers

   1. Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types

      • Lucia Acciai, Michele Boreale

      Pages 31-42

   2. When Are Timed Automata Determinizable?

      • Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye

      Pages 43-54

   3. Faithful Loops for Aperiodic E-Ordered Monoids

      • Martin Beaudry, François Lemieux

      Pages 55-66

   4. Boundedness of Monadic Second-Order Formulae over Finite Words

      • Achim Blumensath, Martin Otto, Mark Weyer

      Pages 67-78

   5. Semilinear Program Feasibility

      • Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

      Pages 79-90

   6. Floats and Ropes: A Case Study for Formal Numerical Program Verification

      • Sylvie Boldo

      Pages 91-102

   7. Reachability in Stochastic Timed Games

      • Patricia Bouyer, Vojtěch Forejt

      Pages 103-114

   8. Equations Defining the Polynomial Closure of a Lattice of Regular Languages

      • Mário J. J. Branco, Jean-Éric Pin

      Pages 115-126

   9. Approximating Markov Processes by Averaging

      • Philippe Chaput, Vincent Danos, Prakash Panangaden, Gordon Plotkin

      Pages 127-138

   10. The Theory of Stabilisation Monoids and Regular Cost Functions

       • Thomas Colcombet

       Pages 139-150

   11. A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata

       • Thomas Colcombet, Konrad Zdanowski

       Pages 151-162

   12. On Constructor Rewrite Systems and the Lambda-Calculus

       • Ugo Dal Lago, Simone Martini

       Pages 163-174

   13. On Regular Temporal Logics with Past,

       • Christian Dax, Felix Klaedtke, Martin Lange

       Pages 175-187

   14. Forward Analysis for WSTS, Part II: Complete WSTS

       • Alain Finkel, Jean Goubault-Larrecq

       Pages 188-199

   15. Qualitative Concurrent Stochastic Games with Imperfect Information

       • Vincent Gripon, Olivier Serre

       Pages 200-211

   16. Diagrammatic Confluence and Completion

       • Jean-Pierre Jouannaud, Vincent van Oostrom

       Pages 212-222

   17. Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus

       • Naoki Kobayashi, C. -H. Luke Ong

       Pages 223-234

ICALP 2009, the 36th edition of the International Colloquium on Automata, Languages and Programming, was held on the island of Rhodes, July 6–10, 2009. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS) which ?rst took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, complexity and games) and track B (focusing on logic, automata, semantics and theory of programming), and of the recently introduced track C (in 2009 focusing on foundations of networked computation). In response to the call for papers, the Program Committee received 370 s- missions: 223 for track A, 84 for track B and 63 for track C. Out of these, 108 papers were selected for inclusion in the scienti?c program: 62 papers for track A, 24 for track B and 22 for track C. The selection was made by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high indeed, and many dese- ing papers could not be selected. ICALP 2009 consisted of ?ve invited lectures and the contributed papers.

• ARC
• algebra
• algorithms
• automata theory
• complexity
• group theory
• lambda calculus
• logic
• monadic logic
• program analysis
• programming
• sorting algorithms
• temporal logic
• wireless networks

• Department of Computer Science, University of Freiburg, Freiburg, Germany

  Susanne Albers

• Department of Computer and Systems Sciences, Sapienza University of Rome, Roma, Italy

  Alberto Marchetti-Spaccamela

• Tel Aviv University Google R&D Center, School of Computer Science, Tel Aviv University, Tel Aviv, Israel

  Yossi Matias

• University of Patras and CTI, Rion, Greece

  Sotiris Nikoletseas

• RWTH Aachen, Aachen, Germany

  Wolfgang Thomas

Policies and ethics