Automata, Languages and Programming

The 28th International Colloquium on Automata, Languages and Programming (ICALP 2001) was held July 8-12, 2001 in the Aldemar-Knossos Royal Village near Hersonissos on Crete, Greece. This volume contains all contributed papers presented at ICALP 2001, together with the invited lectures by Ahmed Bou- jani (Paris), Martin Gro e-Rhode (Berlin), Mogens Nielsen (Aarhus), and Ingo Wegener (Dortmund) and two of the keynote lectures, by Christos Papadimitriou and Boris Trakhtenbrot. For almost 30 years now, ICALP has been the main annual event of the European Association for Theoretical Computer Science (EATCS). The ICALP program currently consists of track A: Algorithms, Automata, Complexity, and Games and track B: Logic, Semantics, and Theory of Programming. In response to the Call for Papers, the program committee received 208 s- missions: 162 for track A, 46 for track B. The committee met on March 23/24, 2001 in Barcelona and selected 80 papers for inclusion into the scienti c program.

Includes supplementary material: sn.pub/extras

Inhalt
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 ObjectOriented System Models.- Modelling with Partial Orders Why and Why Not?.- Theoretical Aspects of Evolutionary Algorithms.- Algebraic and Circuit Complexity.- Improvements of the AlderStrassen 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 ofIterations.- 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 forReversible Simulation.- Finite-State Dimension.- The Complexity of Computing the Size of an Interval.- Communication Gap for Finite Memory Devices.- Separating Quantum and Classical Learning.