Automata, Languages and Programming

This book constitutes the refereed proceedings of the 28th International Colloquium on Automata, Languages and Programming, ICALP 2001, held in Crete, Greece in July 2001. The 80 revised papers presented together with two keynote contributions and four invited papers were carefully reviewed and selected from a total of 208 submissions. The papers are organized in topical sections on algebraic and circuit complexity, algorithm analysis, approximation and optimization, complexity, concurrency, efficient data structures, graph algorithms, language theory, codes and automata, model checking and protocol analysis, networks and routing, reasoning and verification, scheduling, secure computation, specification and deduction, and structural complexity.

Keynote Papers.- Algorithms, Games, and the Internet.- Automata, Circuits, and Hybrids: Facets of Continuous Time.- Invited Papers.- Languages, Rewriting Systems, and Verification of Infinite-State Systems.- Integrating Semantics for Object—Oriented System Models.- Modelling with Partial Orders — Why and Why Not?.- Theoretical Aspects of Evolutionary Algorithms.- Algebraic and Circuit Complexity.- Improvements of the Alder—Strassen Bound: Algebras with Nonzero Radical.- On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities.- Division Is In Uniform TC0.- Algorithm Analysis.- A Framework for Index Bulk Loading and Dynamization.- A Characterization of Temporal Locality and Its Portability across Memory Hierarchies.- The Complexity of Constructing Evolutionary Trees Using Experiments.- Hidden Pattern Statistics.- Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence.- All-Pairs Shortest Paths Computation in the BSP Model.- Approximation and Optimization.- Approximating the Minimum Spanning Tree Weight in Sublinear Time.- Approximation Hardness of TSP with Bounded Metrics.- The RPR 2 Rounding Technique for Semidefinite Programs.- Approximation Algorithms for Partial Covering Problems.- On the Online Bin Packing Problem.- Quick k-Median, k-Center, and Facility Location for Sparse Graphs.- Complexity.- Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems.- Subexponential Parameterized Algorithms Collapse the W-Hierarchy.- Improved Lower Bounds on the Randomized Complexity of Graph Properties.- New Imperfect Random Source with Applications to Coin-Flipping.- Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently.- Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations.- On Interactive Proofs with a Laconic Prover.- Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness.- Lower Bounds in the Quantum Cell Probe Model.- Concurrency.- Axiomatizations for Probabilistic Bisimulation.- Noninterference for Concurrent Programs.- Distributed Controller Synthesis for Local Specifications.- A Distributed Abstract Machine for Safe Ambients.- Towards Quantitative Verification of Probabilistic Transition Systems.- Efficient Datastructures.- Efficient Generation of Plane Triangulations without Repetitions.- The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations.- Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher.- A New Method for Balancing Binary Search Trees.- Graph Algorithms.- Permutation Editing and Matching via Embeddings.- Testing Hypergraph Coloring.- Total Colorings of Degenerated Graphs.- Decidable Properties of Graphs of All-Optical Networks.- Majority Consensus and the Local Majority Rule.- Language Theory, Codes, and Automata.- Solvability of Equations in Free Partially Commutative Groups Is decidable.- Rational Transformations of Formal Power Series.- Combinatorics of Three-Interval Exchanges.- Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages.- The Star Problem in Trace Monoids: Reductions Beyond C4.- The Trace Coding Problem Is Undecidable.- Combinatorics of Periods in Strings.- Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct.- Model Checking and Protocol Analysis.- Effective Lossy Queue Languages.- Model Checking of Unrestricted Hierarchical State Machines.- Symbolic Trace Analysis of Cryptographic Protocols.- Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols.- Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata.- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width.- From Finite State Communication Protocols to High-Level Message Sequence Charts.- Networks and Routing.- Fractional Path Coloring with Applications to WDM Networks.- Performance Aspects of Distributed Caches Using TTL-Based Consistency.- Routing in Trees.- Online Packet Routing on Linear Arrays and Rings.- Faster Gossiping on Butterflies.- Reasoning and Verification.- Realizability and Verification of MSC Graphs.- Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs.- A Set-Theoretic Framework for Assume-Guarantee Reasoning.- Foundations for Circular Compositional Reasoning.- Scheduling.- A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.- The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.- On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates.- On the Approximability of Average Completion Time Scheduling under Precedence Constraints.- Secure Computation.- Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds.- Information-Theoretic Private Information Retrieval: A Unified Construction.- Secure Multiparty Computation of Approximations.- Secure Games with Polynomial Expressions.- Specification and Deduction.- On the Completeness of Arbitrary Selection Strategies for Paramodulation.- An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS.- Knuth-Bendix Constraint Solving Is NP-Complete.- Amalgamation in CASL via Enriched Signatures.- Structural Complexity.- Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution.- Time and Space Bounds for Reversible Simulation.- Finite-State Dimension.- The Complexity of Computing the Size of an Interval.- Communication Gap for Finite Memory Devices.- Separating Quantum and Classical Learning.