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

Ming Li, Paul M. B. Vitányi (auth.), W. Kuich (eds.)3540557199, 9783540557197

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 computer science, including such topics as computability, automata, formal languages, term rewriting, analysis of algorithms, computational geometry, computational complexity, symbolic and algebraic computation, cryptography, data types and data structures, theory of databases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logic programming, theory of logical design andlayout, parallel and distributed computation, theory of concurrency, and theory of robotics. The papers in the volume are grouped into thematic parts corresponding to their order of presentation at ICALP 92.

---

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