Skip to main content
SpringerLink
Log in
Book cover

Automata, Languages and Programming

35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Luca Aceto
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Ivan Damgård
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Leslie Ann Goldberg
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Magnús M. Halldórsson
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Anna Ingólfsdóttir
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  6. Igor Walukiewicz
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5126)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: ICALP 2008.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (58 papers)

  1. Front Matter

    Download chapter 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
Back to top

Other volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Keywords

About this book

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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation