+612 9045 4394
 
CHECKOUT
Automata, Languages and Programming : 19th International Colloquium, Wien, Austria, July 13-17, 1992. Proceedings - Werner Kuich

Automata, Languages and Programming

19th International Colloquium, Wien, Austria, July 13-17, 1992. Proceedings

By: Werner Kuich (Editor)

Paperback

Published: 1st July 1992
Ships: 15 business days
15 business days
$181.29
or 4 easy payments of $45.32 with Learn more

This volume presents the proceedings of the 19thInternational Colloquium onAutomata, Languages, andProgramming (ICALP 92) in a series of meetings sponsored bythe European Association for Theoretical Computer Science(EATCS).ICALP is a broadly based conference covering all aspects oftheoretical computer science, including such topics ascomputability, automata, formal languages, term rewriting,analysis of algorithms, computational geometry,computational complexity, symbolic and algebraiccomputation, cryptography, data types and data structures,theory of databases and knowledge bases, semantics ofprogramming languages, program specification, transformationand verification, foundations of logic programming, theoryof logical design andlayout, parallel and distributedcomputation, theory of concurrency, and theory of robotics.The papers in the volume are grouped into thematic partscorresponding to their order of presentation at ICALP 92.

Complexity (Session 1)
Philosophical Issues in Kolmogorov Complexity (Invited Lecture)p. 1
Circuit Complexity and the Expressive Power of Generalized First-Order Formulasp. 16
One-Message Statistical Zero-Knowledge Proofs and Space-Bounded Verifierp. 28
Formal Languages (Session 2)
Abelian Squares Are Avoidable on 4 Lettersp. 41
Polynomial Size Test Sets for Context-Free Languagesp. 53
Quasi-Deterministic OL Systemsp. 65
On Growing Context-Sensitive Languagesp. 77
Finite Automata (Session 3)
Numeration Systems, Linear Recurrences, and Regular Setsp. 89
The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidablep. 101
Semi-Commutations and Rational Expressionsp. 113
New Results Concerning Synchronized Finite Automatap. 126
Graph Grammars and Complexity (Session 4)
A Greibach Normal Form for Context-Free Graph Grammarsp. 138
On Reverse and General Definite Tree Languagesp. 150
Reductions to Sets of Low Information Contentp. 162
UP and the Low and High Hierarchies: A Relativized Separationp. 174
Algorithm Analysis (Session 5)
Analytic Analysis of Algorithms (Invited Lecture)p. 186
How to Count Quickly and Accuratelyp. 211
The Average CRI-Length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effectsp. 223
Algorithms (Session 6)
Polynomial Hash Functions Are Reliablep. 235
Adaptive Pattern Matchingp. 247
Randomised Interpolation and Approximation of Sparse Polynomialsp. 261
Two Strikes Against Perfect Phylogenyp. 273
Parallel Computation (Session 7)
Disjunctive Systems and L-Domainsp. 284
Optimal Parallel Algorithms for Periods, Palindromes and Squaresp. 296
Near-Perfect Token Distributionp. 308
Fast Integer Merging on the EREW PRAMp. 318
Graph Algorithms (Session 8)
Approximation Algorithms for Graph Augmentationp. 330
Fast Incremental Planarity Testingp. 342
Maintenance of Triconnected Components of Graphsp. 354
Suboptimal Cuts: Their Enumeration, Weight and Numberp. 366
Symbolic Computation (Session 9)
Grobner Bases: An Introduction (Invited Lecture)p. 378
Buchberger's Algorithm: The Term Rewriter's Point of Viewp. 380
Completion of Rewrite Systems with Membership Constraintsp. 392
Geometric Algorithms (Session 10)
A New Metric Between Polygons, and How to Compute itp. 404
On Nearest-Neighbor Graphsp. 416
A Tail Estimate for Mulmuley's Segment Intersection Algorithmp. 427
Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machinep. 439
Logic and Models I (Session 11)
Infinitary Logic for Computer Science (Invited Lecture)p. 450
Characterization of Temporal Property Classesp. 474
Lazy Lambda Calculus: Theories, Models and Local Structure Characterizationp. 487
Logic and Models II (Session 12)
Logic Programming Semantics Made Easyp. 499
On the Complexity of Dataflow Analysis of Logic Programsp. 509
Comparison of Abstract Interpretationsp. 521
A Proposed Categorical Semantics for Pure MLp. 533
Time Specification (Session 13)
What Good Are Digital Clocks?p. 545
Behavioural Abstraction in TCCSp. 559
Timing Petri Nets Categoricallyp. 571
Asynchronous Cellular Automata for Infinite Tracesp. 583
Concurrency Semantics (Session 14)
A Trace Semantics for Petri Netsp. 595
Asynchronous Communication of Petri Nets and the Refinement of Transitionsp. 605
A Parametric Approach to Localitiesp. 617
Proved Treesp. 629
Program Development (Session 15)
Interfaces Between Languages for Communicating Systems (Invited Lecture)p. 641
Toward Formal Development of Programs from Algebraic Specifications: Model-Theoretic Foundations (Invited Lecture)p. 656
Process Equivalences (Session 16)
Program Composition via Unificationp. 672
Barbed Bisimulationp. 685
Checking Equivalences Between Concurrent Systems of Finite Agentsp. 696
Testing Preorders for Probabilistic Processesp. 708
Author Indexp. 721
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540557197
ISBN-10: 3540557199
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 724
Published: 1st July 1992
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.73
Weight (kg): 1.01