Automata, Languages and Programming: 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999 Proceedings (Lecture Notes in Computer Science (1644))

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. Icalp { The International Colloquium On Automata, Languages, And Progr- Ming { Is A Series Of Annual Conferences Of The European Association For Th- Retical Computer Science (eatcs). Icalp’99 Was Organized By The Institute Of Computer Science Of The Academy Of Sciences Of The Czech Republic In - Operation With The Action M Agency. Stimulated By The Positive Experience From Previous Meetings, The Guiding Idea Of The Icalp’99 Organization Was To Keep And To Enhance The Idea Of A Parallel Two{track Conference With Invited Plenary Talks. Similarly To The Two Parts Of The Journal Theoretical Computer Science, Track A Of The Meeting Is Devoted To Algorithms, Automata, Complexity, And Games, And Track B To Logic, Semantics, And Theory Of Programming. The Program Committee Was Structured Along These Same Lines. As A Further Inno- Tion, Icalp’99 Was Coordinated With The European Symposium On Algorithms (esa’99) In Such A Way That Both Conferences Took Place In The Same Location With The Former Immediately Followed By The Latter. Icalp’99 Was The 26th In The Series Of Icalp Colloquia. Previous Colloquia Were Held In Paris (1972), Saarbruc ̈ Ken (1974), Edinburgh (1976), Turku (1977), Udine (1978), Graz (1979), Amsterdam (1980), Haifa (1981), Aarhus (1982), Barcelona (1983), Antwerp (1984), Nafplion (1985), Rennes (1986), Karlsruhe (1987), Tampere (1988), Stresa (1989), Warwick (1990), Madrid (1991), Vienna (1992), Lund (1993), Jerusalem (1994), Szeged (1995), Paderborn (1996), Bo- Gna (1997), And Aalborg (1998). In The Year 2000 Icalp Will Be Held In Geneva. Invited Talks -- Generating Hard Instances Of The Short Basis Problem -- Wide Area Computation -- Proof Techniques For Cryptographic Protocols -- Type Structure For Low-level Programming Languages -- Real Computations With Fake Numbers -- A Model For Associative Memory, A Basis For Thinking And Consciousness -- Numerical Integration With Exact Real Arithmetic -- Observations About The Nature And State Of Computer Science -- Dna Computing: New Ideas And Paradigms -- Online Data Structures In External Memory -- From Computational Learning Theory To Discovery Science -- Contributed Papers -- Bounded Depth Arithmetic Circuits: Counting And Closure -- Parametric Temporal Logic For “model Measuring” -- Communicating Hierarchical State Machines -- Small Pseudo-random Sets Yield Hard Functions: New Tight Explicit Lower Bounds For Branching Programs -- General Morphisms Of Petri Nets (extended Abstract) -- On Some Tighter Inapproximability Results (extended Abstract) --^ Decomposition And Composition Of Timed Automata -- New Applications Of The Incompressibility Method (extended Abstract) -- Mobility Types For Mobile Ambients -- Protein Folding, The Levinthal Paradox And Rapidly Mixing Markov Chains -- Decidable Fragments Of Simultaneous Rigid Reachability -- Text Compression Using Antidictionaries -- Non-interactive Zero-knowledge: A Low-randomness Characterization Of Np (extended Abstract) -- Timed Alternating Tree Automata: The Automata-theoretic Solution To The Tctl Model Checking Problem -- Space-time Tradeoffs For Graph Properties -- Boundedness Of Reset P/t Nets -- Two-way Finite State Transducers And Monadic Second-order Logic -- Partially Ordered Regular Languages For Graph Queries -- Deciding First-order Properties Of Locally Tree-decomposable Graphs -- Comparison Of Process Algebra Equivalences Using Formats -- Compact Routing Tables For Graphs Of Bounded Genus (extended Abstract) -- Computing Logcfl Certificates --^ Efficient Techniques For Maintaining Multidimensional Keys In Linked Data Structures (extended Abstract) -- On The Complements Of Partial K-trees -- Approximation Results For Kinetic Variants Of Tsp -- Distributed Probabilistic Polling And Applications To Proportionate Agreement -- Bisimulation Equivalence Is Decidable For Normed Process Algebra (extended Abstract) -- A Framework For Decidable Metrical Logics -- On The Power Of Las Vegas Ii. Two-way Finite Automata -- Stable Marriage With Incomplete Lists And Ties -- Average-case Complexity Of Shellsort (preliminary Version) -- Linear-time Construction Of Two-dimensional Suffix Trees (extended Abstract) -- A Connection Between The Star Problem And The Finite Power Property In Trace Monoids (extended Abstract) -- Two Techniques In The Area Of The Star Problem -- Approximations By Obdds And The Variable Ordering Problem -- Simulation Preorder On Simple Process Algebras -- Solos In Concert -- Shortest Anisotropic Paths On Terrains --^ Relations Between Local And Global Periodicity Of Words (extended Abstract) -- Efficient Merging, Construction, And Maintenance Of Evolutionary Trees -- Formalizing A Lazy Substitution Proof System For ?-calculus In The Calculus Of Inductive Constructions -- Leader Election By D Dimensional Cellular Automata -- New Upper Bounds For Maxsat -- Polynomial And Rational Evaluation And Interpolation (with Structured Matrices) ? -- Low Redundancy In Static Dictionaries With O(1) Worst Case Lookup Time -- Finite Automata With Generalized Acceptance Criteria -- A Variant Of The Arrow Distributed Directory With Low Average Complexity (extended Abstract) -- Closed Freyd- And ?-categories -- Typed Exceptions And Continuations Cannot Macro-express Each Other -- Automata, Power Series, And Coinduction: Taking Input Derivatives Seriously (extended Abstract) -- Accessing Multiple Sequences Through Set Associative Caches -- T(a) = T(b)? -- Many-valued Logics And Holographic Proofs --^ On The Complexity And Inapproximability Of Shortest Implicant Problems -- The Wave Propagator Is Turing Computable -- An Fptas For Agreeably Weighted Variance On A Single Machine (extended Abstract) -- Erratum: Bulk-synchronous Parallel Multiplication Of Boolean Matrices. Jiří Wiedermann, Peter Van Emde Boas, Mogens Nielsen (eds.) Includes Bibliographical References And Index. 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 A collection of 56 revised papers from ICALP'99 and a further 11 inivited contributions. Topics addressed include approximation algorithms, algebra and circuits, concurrency, semantics and rewriting, process algebras, graphs, distributed computing and the logic of programs.