Automata, Languages and Programming 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999 Proceedings
| Other Authors: | , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1999, 1999
|
| Edition: | 1st ed. 1999 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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
- TypedExceptions 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
- 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 EquivalencesUsing Formats
- Compact Routing Tables for Graphs of Bounded Genus (Extended Abstract)
- Computing LOGCFL Certificates
- 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)
- 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