Automata, Languages and Programming: 19th International Colloquium, Wien, Austria, July 13-17, 1992. Proceedings - Tapa blanda

Sinopsis

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.- 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 of rewrite systems with membership constraints.- 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.- 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.

"Sinopsis" puede pertenecer a otra edición de este libro.