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

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