Automata, Languages and Programming: 27th International Colloquium, ICALP 2000 Geneva, Switzerland, July 9–15, 2000 Proceedings

Samson Abramsky (auth.), Ugo Montanari, José D. P. Rolim, Emo Welzl (eds.)3540677151, 9783540677154

This book constitutes the refereed proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, held in Geneva, Switzerland in July 2000. The 69 revised full papers presented together with nine invited contributions were carefully reviewed and selected from a total of 196 extended abstracts submitted for the two tracks on algorithms, automata, complexity, and games and on logic, semantics, and programming theory. All in all, the volume presents an unique snapshot of the state-of-the-art in theoretical computer science.

---

Table of contents :
Game Semantics: Achievements and Prospects….Pages 1-1
Clique Is Hard to Approximate within n 1 – o (1)….Pages 2-12
Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time….Pages 13-24
Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming….Pages 25-36
A Statically Allocated Parallel Functional Language….Pages 37-48
An Optimal Minimum Spanning Tree Algorithm….Pages 49-60
Improved Shortest Paths on the Word RAM….Pages 61-72
Improved Algorithms for Finding Level Ancestors in Dynamic Trees….Pages 73-84
Lax Logical Relations….Pages 85-102
Reasoning about Idealized ALGOL Using Regular Languages….Pages 103-115
The Measurement Process in Domain Theory….Pages 116-126
Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution….Pages 127-150
Monotone Proofs of the Pigeon Hole Principle….Pages 151-162
Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models….Pages 163-174
Algebraic Models for Contextual Nets….Pages 175-186
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems….Pages 187-198
Measures of Nondeterminism in Finite Automata….Pages 199-210
LTL Is Expressively Complete for Mazurkiewicz Traces….Pages 211-223
An Automata-Theoretic Completeness Proof for Interval Temporal Logic….Pages 223-234
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?….Pages 235-235
Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search….Pages 236-247
Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices….Pages 248-259
Variable Independence, Quantifier Elimination, and Constraint Representations….Pages 260-271
Constraint Satisfaction Problems and Finite Algebras….Pages 272-282
An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing….Pages 283-295
Resource Augmentation for Online Bounded Space Bin Packing….Pages 296-304
Optimal Projective Algorithms for the List Update Problem….Pages 305-316
Efficient Verification Algorithms for One-Counter Processes….Pages 317-328
On the Complexity of Bisimulation Problems for Basic Parallel Processes….Pages 329-341
Decidable First-Order Transition Logics for PA-Processes….Pages 342-353
Non Interference for the Analysis of Cryptographic Protocols….Pages 354-372
Average Bit-Complexity of Euclidean Algorithms….Pages 373-387
Planar Maps and Airy Phenomena….Pages 388-402
Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System….Pages 403-414
Information Flow vs. Resource Access in the Asynchronous Pi-Calculus (Extended Abstract)….Pages 415-427
The Genomics Revolution and Its Challenges for Algorithmic Research….Pages 428-428
Alternating the Temporal Picture for Safety….Pages 429-450
Necessary and Sufficient Assumptions for Non-interactive Zero-Knowledge Proofs of Knowledge for All NP Relations….Pages 451-462
Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP….Pages 463-474
A New Unfolding Approach to LTL Model Checking….Pages 475-486
Reasoning about Message Passing in Finite State Environments….Pages 487-498
Extended Notions of Security for Multicast Public Key Cryptosystems….Pages 499-511
One-Round Secure Computation and Secure Autonomous Mobile Agents….Pages 512-523
Round-Optimal and Abuse-Free Optimistic Multi-party Contract Signing….Pages 524-535
On the Centralizer of a Finite Set….Pages 536-546
On the Power of Tree-Walking Automata….Pages 547-560
Determinization of Transducers over Infinite Words….Pages 561-570
Constraint Programming and Graph Algorithms….Pages 571-575
Scalable Secure Storage when Half the System Is Faulty….Pages 576-587
Generating Partial and Multiple Transversals of a Hypergraph….Pages 588-599
Revisiting the Correspondence between Cut Elimination and Normalisation….Pages 600-611
Negation Elimination from Simple Equational Formulae….Pages 612-623
Hardness of Set Cover with Intersection 1….Pages 624-635
Strong Inapproximability of the Basic k -Spanner Problem….Pages 636-648
Infinite Series-Parallel Posets: Logic and Languages….Pages 648-662
On Deciding if Deterministic Rabin Language Is in Büchi Class….Pages 663-674
On Message Sequence Graphs and Finitely Generated Regular MSC Languages….Pages 675-686
Pseudorandomness….Pages 687-704
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols….Pages 705-717
Deterministic Radio Broadcasting….Pages 717-729
An ω-Complete Equational Specification of Interleaving….Pages 729-743
A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors….Pages 744-755
Tight Size Bounds for Packet Headers in Narrow Meshes….Pages 756-767
Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link….Pages 768-779
On the Logical Characterisation of Performability Properties….Pages 780-792
On the Representation of Timed Polyhedra….Pages 793-807
Min-wise Independent Permutations: Theory and Practice….Pages 808-808
Testing Acyclicity of Directed Graphs in Sublinear Time….Pages 809-820
Computing the Girth of a Planar Graph….Pages 821-831
Lower Bounds Are Not Easier over the Reals: Inside PH….Pages 832-843
Unlearning Helps….Pages 844-856
Fast Approximation Schemes for Euclidean Multi-connectivity Problems….Pages 856-868
Approximate TSP in Graphs with Forbidden Minors….Pages 869-877
Polynomial Time Approximation Schemes for General Multiprocessor Job Shop Scheduling….Pages 878-889
The Many Faces of a Translation….Pages 890-901
Gales and the Constructive Dimension of Individual Sequences….Pages 902-913
The Global Power of Additional Queries to p-Random Oracles….Pages 914-926
Homogenization and the Polynomial Calculus….Pages 926-938