Automata, Languages and Programming Book

	Complexity (Session 1)
	Philosophical Issues in Kolmogorov Complexity (Invited Lecture)	1
	Circuit Complexity and the Expressive Power of Generalized First-Order Formulas	16
	One-Message Statistical Zero-Knowledge Proofs and Space-Bounded Verifier	28
	Formal Languages (Session 2)
	Abelian Squares Are Avoidable on 4 Letters	41
	Polynomial Size Test Sets for Context-Free Languages	53
	Quasi-Deterministic OL Systems	65
	On Growing Context-Sensitive Languages	77
	Finite Automata (Session 3)
	Numeration Systems, Linear Recurrences, and Regular Sets	89
	The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable	101
	Semi-Commutations and Rational Expressions	113
	New Results Concerning Synchronized Finite Automata	126
	Graph Grammars and Complexity (Session 4)
	A Greibach Normal Form for Context-Free Graph Grammars	138
	On Reverse and General Definite Tree Languages	150
	Reductions to Sets of Low Information Content
	UP and the Low and High Hierarchies: A Relativized Separation	174
	Algorithm Analysis (Session 5)
	Analytic Analysis of Algorithms (Invited Lecture)	186
	How to Count Quickly and Accurately	211
	The Average CRI-Length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effects	223
	Algorithms (Session 6)
	Polynomial Hash Functions Are Reliable	235
	Adaptive Pattern Matching	247
	Randomised Interpolation and Approximation of Sparse Polynomials	261
	Two Strikes Against Perfect Phylogeny	273
	Parallel Computation (Session 7)
	Disjunctive Systems and L-Domains	284
	Optimal Parallel Algorithms for Periods, Palindromes and Squares	296
	Near-Perfect Token Distribution	308
	Fast Integer Merging on the EREW PRAM	318
	Graph Algorithms (Session 8)
	Approximation Algorithms for Graph Augmentation	330
	Fast Incremental Planarity Testing	342
	Maintenance of Triconnected Components of Graphs	354
	Suboptimal Cuts: Their Enumeration, Weight and Number	366
	Symbolic Computation (Session 9)
	Grobner Bases: An Introduction (Invited Lecture)	378
	Buchberger's Algorithm: The Term Rewriter's Point of View	380
	Completion of Rewrite Systems with Membership Constraints	392
	Geometric Algorithms (Session 10)
	A New Metric Between Polygons, and How to Compute it	404
	On Nearest-Neighbor Graphs	416
	A Tail Estimate for Mulmuley's Segment Intersection Algorithm	427
	Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine	439
	Logic and Models I (Session 11)
	Infinitary Logic for Computer Science (Invited Lecture)	450
	Characterization of Temporal Property Classes	474
	Lazy Lambda Calculus: Theories, Models and Local Structure Characterization	487
	Logic and Models II (Session 12)
	Logic Programming Semantics Made Easy	499
	On the Complexity of Dataflow Analysis of Logic Programs	509
	Comparison of Abstract Interpretations	521
	A Proposed Categorical Semantics for Pure ML	533
	Time Specification (Session 13)
	What Good Are Digital Clocks?	545
	Behavioural Abstraction in TCCS	559
	Timing Petri Nets Categorically	571
	Asynchronous Cellular Automata for Infinite Traces	583
	Concurrency Semantics (Session 14)
	A Trace Semantics for Petri Nets	595
	Asynchronous Communication of Petri Nets and the Refinement of Transitions	605
	A Parametric Approach to Localities	617
	Proved Trees	629
	Program Development (Session 15)
	Interfaces Between Languages for Communicating Systems (Invited Lecture)	641
	Toward Formal Development of Programs from Algebraic Specifications: Model-Theoretic Foundations (Invited Lecture)	656
	Process Equivalences (Session 16)
	Program Composition via Unification	672
	Barbed Bisimulation	685
	Checking Equivalences Between Concurrent Systems of Finite Agents	696
	Testing Preorders for Probabilistic Processes	708
	Author Index	721