Automata, Languages and Programming: 26th International Colloquium, ICALP’99 Prague, Czech Republic, July 11–15, 1999 Proceedings

Generating Hard Instances of the Short Basis Problem....Pages 1-9
Wide Area Computation....Pages 10-24
Proof Techniques for Cryptographic Protocols....Pages 25-39
Type Structure for Low-Level Programming Languages....Pages 40-54
Real Computations with Fake Numbers....Pages 55-73
A Model for Associative Memory, a Basis for Thinking and Consciousness....Pages 74-89
Numerical Integration with Exact Real Arithmetic....Pages 90-104
Observations about the Nature and State of Computer Science....Pages 105-105
DNA Computing: New Ideas and Paradigms....Pages 106-118
Online Data Structures in External Memory....Pages 119-133
From Computational Learning Theory to Discovery Science....Pages 134-148
Bounded Depth Arithmetic Circuits: Counting and Closure....Pages 149-158
Parametric Temporal Logic for “Model Measuring”....Pages 159-168
Communicating Hierarchical State Machines....Pages 169-178
Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs....Pages 179-189
General Morphisms of Petri Nets (Extended Abstract)....Pages 190-199
On Some Tighter Inapproximability Results (Extended Abstract)....Pages 200-209
Decomposition and Composition of Timed Automata....Pages 210-219
New Applications of the Incompressibility Method (Extended Abstract)....Pages 220-229
Mobility Types for Mobile Ambients....Pages 230-239
Protein Folding, the Levinthal Paradox and Rapidly Mixing Markov Chains....Pages 240-249
Decidable Fragments of Simultaneous Rigid Reachability....Pages 250-260
Text Compression Using Antidictionaries....Pages 261-270
Non-interactive Zero-Knowledge: A Low-Randomness Characterization of NP (Extended Abstract)....Pages 271-280
Timed Alternating Tree Automata: The Automata-Theoretic Solution to the TCTL Model Checking Problem....Pages 281-290
Space-Time Tradeoffs for Graph Properties....Pages 291-300
Boundedness of Reset P/T Nets....Pages 301-310
Two-way finite state transducers and monadic second-order logic....Pages 311-320
Partially Ordered Regular Languages for Graph Queries....Pages 321-330
Deciding First-Order Properties of Locally Tree-Decomposable Graphs....Pages 331-340
Comparison of Process Algebra Equivalences Using Formats....Pages 341-350
Compact Routing Tables for Graphs of Bounded Genus (Extended Abstract)....Pages 351-360
Computing LOGCFL Certificates....Pages 361-371
Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures (Extended Abstract)....Pages 372-381
On the Complements of Partial k -Trees....Pages 382-391
Approximation Results for Kinetic Variants of TSP....Pages 392-401
Distributed Probabilistic Polling and Applications to Proportionate Agreement....Pages 402-411
Bisimulation Equivalence Is Decidable for Normed Process Algebra (Extended abstract)....Pages 412-421
A Framework for Decidable Metrical Logics....Pages 422-432
On the Power of Las Vegas II. Two-Way Finite Automata....Pages 433-442
Stable Marriage with Incomplete Lists and Ties....Pages 443-452
Average-Case Complexity of Shellsort (Preliminary Version) ....Pages 453-462
Linear-Time Construction of Two-Dimensional Suffix Trees (Extended Abstract)....Pages 463-472
A Connection between the Star Problem and the Finite Power Property in Trace Monoids (Extended Abstract)....Pages 473-482
Two Techniques in the Area of the Star Problem....Pages 483-492
Approximations by OBDDs and the Variable Ordering Problem....Pages 493-502
Simulation Preorder on Simple Process Algebras....Pages 503-512
Solos in Concert....Pages 513-523
Shortest Anisotropic Paths on Terrains....Pages 524-533
Relations between Local and Global Periodicity of Words (Extended Abstract)....Pages 534-543
Efficient Merging, Construction, and Maintenance of Evolutionary Trees....Pages 544-553
Formalizing a Lazy Substitution Proof System for π-Calculus in the Calculus of Inductive Constructions....Pages 554-564
Leader Election by d Dimensional Cellular Automata....Pages 565-574
New Upper Bounds for MaxSat....Pages 575-584
Polynomial and Rational Evaluation and Interpolation (with Structured Matrices) ⋆....Pages 585-594
Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time....Pages 595-604
Finite Automata with Generalized Acceptance Criteria....Pages 605-614
A Variant of the Arrow Distributed Directory with Low Average Complexity (Extended Abstract)....Pages 615-624
Closed Freyd- and κ -categories....Pages 625-634
Typed Exceptions and Continuations Cannot Macro-Express Each Other....Pages 635-644
Automata, Power Series, and Coinduction: Taking Input Derivatives Seriously (Extended Abstract)....Pages 645-654
Accessing Multiple Sequences Through Set Associative Caches....Pages 655-664
T(A) = T(B)?....Pages 665-675
Many-Valued Logics and Holographic Proofs....Pages 676-686
On the Complexity and Inapproximability of Shortest Implicant Problems....Pages 687-696
The Wave Propagator Is Turing Computable....Pages 697-706
An FPTAS for Agreeably Weighted Variance on a Single Machine (Extended Abstract)....Pages 707-716
Erratum: Bulk-Synchronous Parallel Multiplication of Boolean Matrices....Pages 717-718