Automata, Languages and Programming

1. Front Matter

   PDF

2. Invited Lectures

   1. Holographic Circuits

      • Leslie G. Valiant

      Pages 1-15

   2. Probabilistic Polynomial-Time Semantics for a Protocol Security Logic

      • Anupam Datta, Ante Derek, John C. Mitchell, Vitaly Shmatikov, Mathieu Turuani

      Pages 16-29

   3. A Gentle Introduction to Semantic Subtyping

      • Giuseppe Castagna, Alain Frisch

      Pages 30-34

   4. Logics for Unranked Trees: An Overview

      • Leonid Libkin

      Pages 35-50

   5. Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture

      • Martin Gairing, Thomas Lücking, Burkhard Monien, Karsten Tiemann

      Pages 51-65

3. Data Structures I

   1. The Tree Inclusion Problem: In Optimal Space and Faster

      • Philip Bille, Inge Li Gørtz

      Pages 66-77

   2. Union-Find with Constant Time Deletions

      • Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick

      Pages 78-89

   3. Optimal In-place Sorting of Vectors and Records

      • Gianni Franceschini, Roberto Grossi

      Pages 90-102

   4. Towards Optimal Multiple Selection

      • Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders

      Pages 103-114

4. Cryptography and Complexity

   1. Simple Extractors via Constructions of Cryptographic Pseudo-random Generators

      • Marius Zimand

      Pages 115-127

   2. Bounds on the Efficiency of “Black-Box” Commitment Schemes

      • Omer Horvitz, Jonathan Katz

      Pages 128-139

   3. On Round-Efficient Argument Systems

      • Hoeteck Wee

      Pages 140-152

   4. Computational Bounds on Hierarchical Data Processing with Applications to Information Security

      • Roberto Tamassia, Nikos Triandopoulos

      Pages 153-165

5. Data Structures II

   1. Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins

      • Martin Dietzfelbinger, Christoph Weidling

      Pages 166-178

   2. Worst Case Optimal Union-Intersection Expression Evaluation

      • Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh

      Pages 179-190

   3. Measure and Conquer: Domination – A Case Study

      • Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch

      Pages 191-203

6. Cryptography and Distributed Systems

   1. Optimistic Asynchronous Atomic Broadcast

      • Klaus Kursawe, Victor Shoup

      Pages 204-215

   2. Asynchronous Perfectly Secure Communication over One-Time Pads

      • Giovanni Di Crescenzo, Aggelos Kiayias

      Pages 216-227

   3. Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds

      • Giuseppe Persiano, Ivan Visconti

      Pages 228-240

The 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) was held in Lisbon, Portugal from July 11 to July 15, 2005. These proceedings contain all contributed papers presented at ICALP 2005, - getherwiththepapersbytheinvitedspeakersGiuseppeCastagna(ENS),Leonid Libkin (Toronto), John C. Mitchell (Stanford), Burkhard Monien (Paderborn), and Leslie Valiant (Harvard). The program had an additional invited lecture by Adi Shamir (Weizmann Institute) which does not appear in these proceedings. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS). The ?rst ICALP took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, automata, complexity and games) and track B (focusing on logic, semantics and theory of programming), and innovated on the structure of its traditional scienti?c program with the inauguration of a new track C (focusing on security and cryptography foundation). In response to a call for papers, the Program Committee received 407 s- missions, 258 for track A, 75 for track B and 74 for track C. This is the highest number of submitted papers in the history of the ICALP conferences. The P- gram Committees selected 113 papers for inclusion in the scienti?c program. In particular, the Program Committee for track A selected 65 papers, the P- gram Committee for track B selected 24 papers, and the Program Committee for track C selected 24 papers. All the work of the Program Committees was done electronically.

• Automat
• algorithms
• automata
• complexity
• computer science
• data structures
• distributed systems
• formal language
• formal languages
• game theory
• logic
• model checking
• programming
• verification

• CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal

  Luís Caires

• Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Roma, Italy

  Giuseppe F. Italiano

• Departamento de Informatica, Universidade Nova de Lisboa, Caparica, Portugal

  Luís Monteiro

• Ecole Polytechnique, Palaiseau Cedex, France

  Catuscia Palamidessi

• Computer Science Department, Google Inc. and Columbia University, New York, USA

  Moti Yung

Policies and ethics