Automata, Languages and Programming: 19th International Colloquium Wien, Austria, July 13–17, 1992 Proceedings

Philosophical issues in Kolmogorov complexity....Pages 1-15
Circuit complexity and the expressive power of generalized first-order formulas....Pages 16-27
One-message statistical Zero-Knowledge Proofs and space-bounded verifier....Pages 28-40
Abelian squares are avoidable on 4 letters....Pages 41-52
Polynomial size test sets for context-free languages....Pages 53-64
Quasi-deterministic 0L systems....Pages 65-76
On growing context-sensitive languages....Pages 77-88
Numeration systems, linear recurrences, and regular sets....Pages 89-100
The equality problem for rational series with multiplicities in the tropical semiring is undecidable....Pages 101-112
Semi-commutations and rational expressions....Pages 113-125
New results concerning synchronized finite automata....Pages 126-137
A Greibach normal form for context-free graph grammars....Pages 138-149
On reverse and general definite tree languages....Pages 150-161
Reductions to sets of low information content....Pages 162-173
UP and the low and high hierarchies: A relativized separation....Pages 174-185
Analytic analysis of algorithms....Pages 186-210
How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems....Pages 211-222
The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects....Pages 223-234
Polynomial hash functions are reliable....Pages 235-246
Adaptive pattern matching....Pages 247-260
Randomized interpolation and approximation of sparse polynomials stPreliminary version....Pages 261-272
Two strikes against perfect phylogeny....Pages 273-283
Disjunctive systems and L-Domains....Pages 284-295
Optimal parallel algorithms for periods, palindromes and squares....Pages 296-307
Near-perfect token distribution....Pages 308-317
Fast integer merging on the EREW PRAM....Pages 318-329
Approximation algorithms for graph augmentation....Pages 330-341
Fast incremental planarity testing....Pages 342-353
Maintenance of triconnected components of graphs....Pages 354-365
Suboptimal cuts: Their enumeration, weight and number....Pages 366-377
Gröbner bases: An introduction....Pages 378-379
Buchberger\'s algorithm: The term rewriter\'s point of view....Pages 380-391
Completion of rewrite systems with membership constraints....Pages 392-403
A new metric between polygons, and how to compute it....Pages 404-415
On nearest-neighbor graphs....Pages 416-426
A tail estimate for Mulmuley\'s segment intersection algorithm....Pages 427-438
Lower bounds on the complexity of simplex range reporting on a pointer machine....Pages 439-449
Infinitary logic for computer science....Pages 450-473
Characterization of temporal property classes....Pages 474-486
Lazy Lambda calculus: Theories, models and local structure characterization....Pages 487-498
Logic programming semantics made easy....Pages 499-508
On the complexity of dataflow analysis of logic programs....Pages 509-520
Comparison of abstract interpretations....Pages 521-532
A proposed categorical semantics for Pure ML....Pages 533-544
What good are digital clocks?....Pages 545-558
Behavioural abstraction in TCCS....Pages 559-570
Timing Petri Nets categorically....Pages 571-582
Asynchronous cellular automata for infinite traces....Pages 583-594
A trace semantics for Petri Nets....Pages 595-604
Asynchronous communication of Petri Nets and the refinement of transitions....Pages 605-616
A parametric approach to localities....Pages 617-628
Proved trees....Pages 629-640
Interfaces between languages for communicating systems....Pages 641-655
Toward formal development of programs from algebraic specifications: Model-theoretic foundations....Pages 656-671
Program composition via unification....Pages 672-684
Barbed bisimulation....Pages 685-695
Checking equivalences between concurrent systems of finite agents (Extended abstract)....Pages 696-707
Testing preorders for probabilistic processes....Pages 708-719