Automata, Languages and Programming

1. Front Matter

   PDF

2. Invited Lectures

   1. Composable Formal Security Analysis: Juggling Soundness, Simplicity and Efficiency

      • Ran Canetti

      Pages 1-13

   2. Newton’s Method for ω-Continuous Semirings

      • Javier Esparza, Stefan Kiefer, Michael Luttenberger

      Pages 14-26

3. Track B: Logic, Semantics, and Theory of Programming

   1. Bounds

      1. The Tractability Frontier for NFA Minimization

         • Henrik Björklund, Wim Martens

         Pages 27-38

      2. Finite Automata, Digraph Connectivity, and Regular Expression Size

         • Hermann Gruber, Markus Holzer

         Pages 39-50

      3. Leftist Grammars Are Non-primitive Recursive

         • Tomasz Jurdziński

         Pages 51-62

      4. On the Computational Completeness of Equations over Sets of Natural Numbers

         • Artur Jeż, Alexander Okhotin

         Pages 63-74

   2. Distributed Computation

      1. Placement Inference for a Client-Server Calculus

         • Matthias Neubauer, Peter Thiemann

         Pages 75-86

      2. Extended pi-Calculi

         • Magnus Johansson, Joachim Parrow, Björn Victor, Jesper Bengtson

         Pages 87-98

      3. Completeness and Logical Full Abstraction in Modal Logics for Typed Mobile Processes

         • Martin Berger, Kohei Honda, Nobuko Yoshida

         Pages 99-111

   3. Real-Time and Probabilistic Systems

      1. On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases

         • Bernard Boigelot, Julien Brusten, Véronique Bruyère

         Pages 112-123

      2. On Expressiveness and Complexity in Real-Time Model Checking

         • Patricia Bouyer, Nicolas Markey, Joël Ouaknine, James Worrell

         Pages 124-135

      3. STORMED Hybrid Systems

         • Vladimeros Vladimerou, Pavithra Prabhakar, Mahesh Viswanathan, Geir Dullerud

         Pages 136-147

      4. Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives

         • Tomáš Brázdil, Vojtěch Forejt, Antonín Kučera

         Pages 148-159

   4. Logic and Complexity

      1. On Datalog vs. LFP

         • Anuj Dawar, Stephan Kreutzer

         Pages 160-171

      2. Directed <i>st</i>-Connectivity Is Not Expressible in Symmetric Datalog

         • László Egri, Benoît Larose, Pascal Tesson

         Pages 172-183

      3. Non-dichotomies in Constraint Satisfaction Complexity

         • Manuel Bodirsky, Martin Grohe

         Pages 184-196

      4. Quantified Constraint Satisfaction and the Polynomially Generated Powers Property

         • Hubie Chen

         Pages 197-208

   5. Words and Trees

      1. When Does Partial Commutative Closure Preserve Regularity?

         • Antonio Cano Gómez, Giovanna Guaiana, Jean-Éric Pin

         Pages 209-220

      2. Weighted Logics for Nested Words and Algebraic Formal Power Series

         • Christian Mathissen

         Pages 221-232

The two-volume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008. The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5126 contains 56 contributions of track B and track C selected from 208 submissions and 2 invited lectures. The papers for track B are organized in topical sections on bounds, distributed computation, real-time and probabilistic systems, logic and complexity, words and trees, nonstandard models of computation, reasoning about computation, and verification. The papers of track C cover topics in security and cryptography such as theory, secure computation, two-party protocols and zero-knowledge, encryption with special properties/quantum cryptography, various types of hashing, as well as public-key cryptography and authentication.

• Hashing
• algorithms
• complexity
• computational mathematics
• cryptography
• cryptology
• formal methods
• game theory
• logic
• logical foundations
• mathematical logic
• program semantics
• programming
• proof complexity
• verification
• data structures

Policies and ethics