Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings

Algorithms, Games, and the Internet....Pages 1-3
Automata, Circuits, and Hybrids: Facets of Continuous Time....Pages 4-23
Languages, Rewriting Systems, and Verification of Infinite-State Systems....Pages 24-39
Integrating Semantics for Object—Oriented System Models....Pages 40-60
Modelling with Partial Orders — Why and Why Not?....Pages 61-63
Theoretical Aspects of Evolutionary Algorithms....Pages 64-78
Improvements of the Alder—Strassen Bound: Algebras with Nonzero Radical....Pages 79-91
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities....Pages 92-103
Division Is In Uniform TC 0 ....Pages 104-114
A Framework for Index Bulk Loading and Dynamization....Pages 115-127
A Characterization of Temporal Locality and Its Portability across Memory Hierarchies....Pages 128-139
The Complexity of Constructing Evolutionary Trees Using Experiments....Pages 140-151
Hidden Pattern Statistics....Pages 152-165
Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence....Pages 166-177
All-Pairs Shortest Paths Computation in the BSP Model....Pages 178-189
Approximating the Minimum Spanning Tree Weight in Sublinear Time....Pages 190-200
Approximation Hardness of TSP with Bounded Metrics....Pages 201-212
The RPR 2 Rounding Technique for Semidefinite Programs....Pages 213-224
Approximation Algorithms for Partial Covering Problems....Pages 225-236
On the Online Bin Packing Problem....Pages 237-248
Quick k -Median, k -Center, and Facility Location for Sparse Graphs....Pages 249-260
Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems....Pages 261-272
Subexponential Parameterized Algorithms Collapse the W-Hierarchy....Pages 273-284
Improved Lower Bounds on the Randomized Complexity of Graph Properties....Pages 285-296
New Imperfect Random Source with Applications to Coin-Flipping....Pages 297-309
Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently....Pages 310-321
Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations....Pages 322-333
On Interactive Proofs with a Laconic Prover....Pages 334-345
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness....Pages 346-357
Lower Bounds in the Quantum Cell Probe Model....Pages 358-369
Axiomatizations for Probabilistic Bisimulation....Pages 370-381
Noninterference for Concurrent Programs....Pages 382-395
Distributed Controller Synthesis for Local Specifications....Pages 396-407
A Distributed Abstract Machine for Safe Ambients....Pages 408-420
Towards Quantitative Verification of Probabilistic Transition Systems....Pages 421-432
Efficient Generation of Plane Triangulations without Repetitions....Pages 433-443
The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations....Pages 444-455
Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher....Pages 456-468
A New Method for Balancing Binary Search Trees....Pages 469-480
Permutation Editing and Matching via Embeddings....Pages 481-492
Testing Hypergraph Coloring....Pages 493-505
Total Colorings of Degenerated Graphs....Pages 506-517
Decidable Properties of Graphs of All-Optical Networks....Pages 518-529
Majority Consensus and the Local Majority Rule....Pages 530-542
Solvability of Equations in Free Partially Commutative Groups Is decidable....Pages 543-554
Rational Transformations of Formal Power Series....Pages 555-566
Combinatorics of Three-Interval Exchanges....Pages 567-578
Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages....Pages 579-590
The Star Problem in Trace Monoids: Reductions Beyond C4....Pages 591-602
The Trace Coding Problem Is Undecidable....Pages 603-614
Combinatorics of Periods in Strings....Pages 615-626
Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct....Pages 627-638
Effective Lossy Queue Languages....Pages 639-651
Model Checking of Unrestricted Hierarchical State Machines....Pages 652-666
Symbolic Trace Analysis of Cryptographic Protocols....Pages 667-681
Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols....Pages 682-693
Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata....Pages 694-707
Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width....Pages 708-719
From Finite State Communication Protocols to High-Level Message Sequence Charts....Pages 720-731
Fractional Path Coloring with Applications to WDM Networks....Pages 732-743
Performance Aspects of Distributed Caches Using TTL-Based Consistency....Pages 744-756
Routing in Trees....Pages 757-772
Online Packet Routing on Linear Arrays and Rings....Pages 773-784
Faster Gossiping on Butterflies....Pages 785-796
Realizability and Verification of MSC Graphs....Pages 797-808
Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs....Pages 809-820
A Set-Theoretic Framework for Assume-Guarantee Reasoning....Pages 821-834
Foundations for Circular Compositional Reasoning....Pages 835-847
A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines....Pages 848-861
The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts....Pages 862-874
On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates....Pages 875-886
On the Approximability of Average Completion Time Scheduling under Precedence Constraints....Pages 887-897
Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds....Pages 898-911
Information-Theoretic Private Information Retrieval: A Unified Construction....Pages 912-926
Secure Multiparty Computation of Approximations....Pages 927-938
Secure Games with Polynomial Expressions....Pages 939-950
On the Completeness of Arbitrary Selection Strategies for Paramodulation....Pages 951-962
An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS....Pages 963-978
Knuth-Bendix Constraint Solving Is NP-Complete....Pages 979-992
Amalgamation in CASL via Enriched Signatures....Pages 993-1004
Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution....Pages 1005-1016
Time and Space Bounds for Reversible Simulation....Pages 1017-1027
Finite-State Dimension....Pages 1028-1039
The Complexity of Computing the Size of an Interval....Pages 1040-1051
Communication Gap for Finite Memory Devices....Pages 1052-1064
Separating Quantum and Classical Learning....Pages 1065-1080