Automata, Languages and Programming 19th International Colloquium, Wien, Austria, July 13-17, 1992. Proceedings
This volume presents the proceedings of the 19th International Colloquium onAutomata, Languages, and Programming (ICALP 92) in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS). ICALP is a broadly based conference covering all aspects of theoretical...
Other Authors: | |
---|---|
Format: | eBook |
Language: | English |
Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1992, 1992
|
Edition: | 1st ed. 1992 |
Series: | Lecture Notes in Computer Science
|
Subjects: | |
Online Access: | |
Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- Philosophical issues in Kolmogorov complexity
- Circuit complexity and the expressive power of generalized first-order formulas
- One-message statistical Zero-Knowledge Proofs and space-bounded verifier
- Abelian squares are avoidable on 4 letters
- Polynomial size test sets for context-free languages
- Quasi-deterministic 0L systems
- On growing context-sensitive languages
- Numeration systems, linear recurrences, and regular sets
- The equality problem for rational series with multiplicities in the tropical semiring is undecidable
- Semi-commutations and rational expressions
- New results concerning synchronized finite automata
- A Greibach normal form for context-free graph grammars
- On reverse and general definite tree languages
- Reductions to sets of low information content
- UP and the low and high hierarchies: A relativized separation
- Analytic analysis of algorithms
- A new metric between polygons, and how to compute it
- On nearest-neighbor graphs
- A tail estimate for Mulmuley's segment intersection algorithm
- Lower bounds on the complexity of simplex range reporting on a pointer machine
- Infinitary logic for computer science
- Characterization of temporal property classes
- Lazy Lambda calculus: Theories, models and local structure characterization
- Logic programming semantics made easy
- On the complexity of dataflow analysis of logic programs
- Comparison of abstract interpretations
- A proposed categorical semantics for Pure ML
- What good are digital clocks?
- Behavioural abstraction in TCCS
- Timing Petri Nets categorically
- Asynchronous cellular automata for infinite traces
- A trace semantics for Petri Nets
- Asynchronous communication of Petri Nets and the refinement of transitions
- A parametric approach to localities
- Proved trees
- Interfaces between languages for communicating systems
- How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems
- The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects
- Polynomial hash functions are reliable
- Adaptive pattern matching
- Randomized interpolation and approximation of sparse polynomials stPreliminary version
- Two strikes against perfect phylogeny
- Disjunctive systems and L-Domains
- Optimal parallel algorithms for periods, palindromes and squares
- Near-perfect token distribution
- Fast integer merging on the EREW PRAM
- Approximation algorithms for graph augmentation
- Fast incremental planarity testing
- Maintenance of triconnected components of graphs
- Suboptimal cuts: Their enumeration, weight and number
- Gröbner bases: An introduction
- Buchberger's algorithm: The term rewriter's point of view
- Completion ofrewrite systems with membership constraints
- Toward formal development of programs from algebraic specifications: Model-theoretic foundations
- Program composition via unification
- Barbed bisimulation
- Checking equivalences between concurrent systems of finite agents (Extended abstract)
- Testing preorders for probabilistic processes