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

Miklós Ajtai (auth.), Jiří Wiedermann, Peter van Emde Boas, Mogens Nielsen (eds.)3540662243, 9783540662242

This book constitutes the refereed proceedings of the 26th International Colloquium on Automata, Languages and Programming, ICALP’99, held in Prague, Czech Republic, in July 1999. The 56 revised full papers presented were carefully reviewed and selected from a total of 126 submissions; also included are 11 inivited contributions. Among the topics addressed are approximation algorithms, algebra and circuits, concurrency, semantics and rewriting, process algebras, graphs, distributed computing, logic of programs, sorting and searching, automata, nonstandard computing, regular languages, combinatorial optimization, automata and logics, string algorithms, and applied logics.

---

Table of contents :
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