• 
  Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger (Eds.): Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings. Springer 2003 Lecture Notes in Computer Science ISBN 3-540-40493-7

Invited Lectures

• 
  Jan A. Bergstra, Inge Bethke: Polarized Process Algebra and Program Equivalence. 1-21
• 
  Anne Condon: Problems on RNA Secondary Structure Prediction and Design. 22-32
• 
  Amos Fiat: Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks. 33
• 
  Petra Mutzel: The SPQR-Tree Data Structure in Graph Drawing. 34-46
• 
  Doron Peled: Model Checking and Testing Combined. 47-63
• 
  Moshe Y. Vardi: Logic and Automata: A Match Made in Heaven. 64-65

Algorithms

• 
  Juraj Hromkovic, Georg Schnitger: Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes. 66-80
• 
  Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro: Generalized Framework for Selectors with Applications in Optimal Group Testing. 81-96
• 
  Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung: Decoding of Interleaved Reed Solomon Codes over Noisy Data. 97-108

Process Algebra

• 
  Stefan Blom, Wan Fokkink, Sumit Nain: On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces. 109-118
• 
  Daniele Gorla, Rosario Pugliese: Resource Access and Mobility Control with Dynamic Privileges Acquisition. 119-132
• 
  Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro: Replication vs. Recursive Definitions in Channel Based Calculi. 133-144

Approximation Algorithms

• 
  Alexander A. Ageev, Yinyu Ye, Jiawei Zhang: Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem. 145-156
• 
  Markus Bläser: An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. 157-163
• 
  Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan: An Improved Approximation Algorithm for Vertex Cover with Hard Capacities. 164-175
• 
  Sanjeev Arora, Kevin L. Chang: Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. 176-188
• 
  Chandra Chekuri, Sudipto Guha, Joseph Naor: Approximating Steiner k-Cuts. 189-199
• 
  Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani: MAX k-CUT and Approximating the Chromatic Number of Random Graphs. 200-211
• 
  Michael Elkin, Guy Kortsarz: Approximation Algorithm for Directed Telephone Multicast Problem. 212-223

Languages and Programming

• 
  Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca: Mixin Modules and Computational Effects. 224-238
• 
  Alexander Okhotin: Decision Problems for Language Equations with Boolean Operations. 239-251
• 
  Roberto Bruni, José Meseguer: Generalized Rewrite Theories. 252-266

Complexity

• 
  Luis Antunes, Lance Fortnow: Sophistication Revisited. 267-277
• 
  John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo: Scaled Dimension and Nonuniform Complexity. 278-290
• 
  Peter Høyer, Michele Mosca, Ronald de Wolf: Quantum Search on Bounded-Error Inputs. 291-299
• 
  Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen: A Direct Sum Theorem in Communication Complexity via Message Compression. 300-315

Data Structures

• 
  Gianni Franceschini, Roberto Grossi: Optimal Cache-Oblivious Implicit Dictionaries. 316-331
• 
  Anna Gál, Peter Bro Miltersen: The Cell Probe Complexity of Succinct Data Structures. 332-344
• 
  J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao: Succinct Representations of Permutations. 345-356
• 
  Rajeev Raman, S. Srinivasa Rao: Succinct Dynamic Dictionaries and Trees. 357-368

Graph Algorithms

• 
  Amos Korman, David Peleg: Labeling Schemes for Weighted Dynamic Trees. 369-383
• 
  Surender Baswana, Sandeep Sen: A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n^1+1/k) Size in Weighted Graphs. 384-296
• 
  Alexander Hall, Steffen Hippler, Martin Skutella: Multicommodity Flows over Time: Efficient Algorithms and Complexity. 397-409
• 
  Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd: Multicommodity Demand Flow in a Tree. 410-425

Automata

• 
  Manfred Droste, Dietrich Kuske: Skew and Infinitary Formal Power Series. 426-438
• 
  Juraj Hromkovic, Georg Schnitger: Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation. 439-451
• 
  François Denis, Yann Esposito: Residual Languages and Probabilistic Automata. 452-463
• 
  Mariëlle Stoelinga, Frits W. Vaandrager: A Testing Scenario for Probabilistic Automata. 464-477
• 
  Géraud Sénizergues: The Equivalence Problem for t-Turn DPDA Is Co-NP. 478-489
• 
  Markus Holzer, Martin Kutrib: Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k. 490-501

Optimization and Games

• 
  Eyal Even-Dar, Alexander Kesselman, Yishay Mansour: Convergence Time to Nash Equilibria. 502-513
• 
  Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode: Nashification and the Coordination Ratio for a Selfish Routing Game. 514-526
• 
  Vipul Bansal, Aseem Agrawal, Varun S. Malhotra: Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution. 527-542
• 
  Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino: An Intersection Inequality for Discrete Distributions and Related Generation Problems. 543-555

Graphs and Bisimulation

• 
  Thierry Cachat: Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games. 556-569
• 
  Richard Mayr: Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes. 570-583
• 
  Massimo Merro, Francesco Zappa Nardelli: Bisimulation Proof Methods for Mobile Ambients. 584-598
• 
  Arnaud Carayol, Thomas Colcombet: On Equivalent Representations of Infinite Structures. 599-610

Online Problems

• 
  Arnold Schönhage: Adaptive Raising Strategies Optimizing Relative Efficiency. 611-623
• 
  René Sitters, Leen Stougie, Willem de Paepe: A Competitive Algorithm for the General 2-Server Problem. 624-636
• 
  Dimitris Fotakis: On the Competitive Ratio for Online Facility Location. 637-652
• 
  Susanne Albers, Rob van Stee: A Study of Integrated Document and Connection Caching. 653-667

Verification

• 
  Gaoyan Xie, Zhe Dang, Oscar H. Ibarra: A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems. 668-680
• 
  Felix Klaedtke, Harald Rueß: Monadic Second-Order Logics with Cardinalities. 681-696
• 
  Orna Kupferman, Moshe Y. Vardi: Pi₂ cap Sigma₂ equiv AFMC. 697-713
• 
  Tatiana Rybina, Andrei Voronkov: Upper Bounds for a Theory of Queues. 714-724

Around the Internet

• 
  Noam Berger, Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Oliver Riordan: Degree Distribution of the FKP Network Model. 725-738
• 
  Vincent D. Blondel, Paul Van Dooren: Similarity Matrices for Pairs of Graphs. 739-750
• 
  Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor: Algorithmic Aspects of Bandwidth Trading. 751-766

Temporal Logic and Model Checking

• 
  Jan Johannsen, Martin Lange: CTL⁺ Is Complete for Double Exponential Time. 767-775
• 
  Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato: Hierarchical and Recursive State Machines with Context-Dependent Properties. 776-789
• 
  Ph. Schnoebelen: Oracle Circuits for Branching-Time Model Checking. 790-801

Graph Problems

• 
  Luisa Gargano, Mikael Hammar: There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them). 802-816
• 
  Jirí Fiala, Daniël Paulusma: The Computational Complexity of the Role Assignment Problem. 817-828
• 
  Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos: Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs. 829-844
• 
  Jianer Chen, Iyad A. Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia: Genus Characterizes the Complexity of Graph Problems: Some Tight Results. 845-856

Logic and Lambda-Calculus

• 
  Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac, David Van Campenhout: The Definition of a Temporal Clock Operator. 857-870
• 
  Zena M. Ariola, Hugo Herbelin: Minimal Classical Logic and Control Operators. 871-885
• 
  Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar: Counterexample-Guided Control. 886-902
• 
  Jo Erskine Hannay: Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types. 903-917

Data Structures and Algorithms

• 
  Yossi Matias, Ely Porat: Efficient Pebbling for List Traversal Synopses. 918-928
• 
  Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat: Function Matching: Algorithms, Applications, and a Lower Bound. 929-942
• 
  Juha Kärkkäinen, Peter Sanders: Simple Linear Work Suffix Array Construction. 943-955

Types and Categories

• 
  Francisco Gutiérrez, Blas C. Ruiz: Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems. 956-968
• 
  Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro Sassone: Secrecy in Untrusted Networks. 969-983
• 
  Arkadev Chattopadhyay, Denis Thérien: Locally Commutative Categories. 984-995

Probabilistic Systems

• 
  Ernst-Erich Doberkat: Semi-pullbacks and Bisimulations in Categories of Stochastic Relations. 996-1007
• 
  Alexander Moshe Rabinovich: Quantitative Analysis of Probabilistic Lossy Channel Systems. 1008-1021
• 
  Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar: Discounting the Future in Systems Theory. 1022-1037
• 
  Luca de Alfaro, Marco Faella: Information Flow in Concurrent Games. 1038-1053

Sampling and Randomness

• 
  Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita: Impact of Local Topological Information on Random Walks on Finite Graphs. 1054-1067
• 
  Jens Jägersküpper: Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces. 1068-1079
• 
  Dominique Poulalhon, Gilles Schaeffer: Optimal Coding and Sampling of Triangulations. 1080-1094
• 
  Manuel Bodirsky, Clemens Gröpl, Mihyun Kang: Generating Labeled Planar Graphs Uniformly at Random. 1095-1107

Scheduling

• 
  Pierluigi Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, Walter Unger: Online Load Balancing Made Simple: Greedy Strikes Back. 1108-1122
• 
  Joseph Naor, Hadas Shachnai, Tami Tamir: Real-Time Scheduling with a Budget. 1123-1137
• 
  Brian C. Dean, Michel X. Goemans: Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. 1138-1152
• 
  Baruch Awerbuch, André Brinkmann, Christian Scheideler: Anycasting in Adversarial Systems: Routing and Admission Control. 1153-1168

Geometric Problems

• 
  Sergei Bespamyatnikh, Michael Segal: Dynamic Algorithms for Approximating Interdistances. 1169-1180
• 
  Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro: Solving the Robots Gathering Problem. 1181-1196