Automata, Languages and Programming: Ninth Colloquium Aarhus, Denmark, July 12–16, 1982

R. J. R. Back, H. Mannila (auth.), Mogens Nielsen, Erik Meineche Schmidt (eds.)9780387115764, 0387115765, 3540115765

This book constitutes the refereed proceedings of the 26th International Colloquium on Automata, Languages and Programming, ICALP’99, held in Prague, Czech Republic, in July 1999. The 56 revised full papers presented were carefully reviewed and selected from a total of 126 submissions; also included are 11 inivited contributions. Among the topics addressed are approximation algorithms, algebra and circuits, concurrency, semantics and rewriting, process algebras, graphs, distributed computing, logic of programs, sorting and searching, automata, nonstandard computing, regular languages, combinatorial optimization, automata and logics, string algorithms, and applied logics.

---

Table of contents :
Locality in modular systems….Pages 1-13
On-the-fly garbage collection: New algorithms inspired by program proofs….Pages 14-22
Algebraic specifications for parametrized data types with minimal parameter and target algebras….Pages 23-34
A modification of the λ-calculus as a base for functional programming languages….Pages 35-47
On the power of nondeterminism in dynamic logic….Pages 48-60
Equivalence and membership problems for regular trace languages….Pages 61-71
On the power of chain rules in context free grammars….Pages 72-82
Extended Chomsky-Schützenberger theorems….Pages 83-93
Real time agents….Pages 94-106
Machine inductive inference and language identification….Pages 107-115
Approximations of infinitary objects….Pages 116-127
On test sets and the Ehrenfeucht conjecture….Pages 128-140
An automata-theoretic characterization of the OI-hierarchy….Pages 141-153
Fast detection of polyhedral intersections….Pages 154-165
On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store….Pages 166-175
Multihead finite state automata am concatenation….Pages 176-186
Conditions enforcing regularity of context-free languages….Pages 187-191
Repetitions in homomorphisms and languages….Pages 192-196
Parameter passing commutes with implementation of parameterized data types….Pages 197-211
An operational semantics for pure dataflow….Pages 212-224
Some properties of D-continuous causal nets….Pages 225-238
A branching process arising in dynamic hashing, trie searching and polynomial factorization….Pages 239-251
A sound and complete HOARE axiomatization of the ADA-rendezvous….Pages 252-264
Universal realization, persistent interconnection and implementation of abstract modules….Pages 265-281
Heaps on heaps….Pages 282-291
A boundary of isomorphism completeness in the lattice of semigroup pseudovarieties….Pages 292-299
Derived Pairs, overlap closures, and rewrite dominoes: New tools for analyzing term rewriting systems….Pages 300-312
A programming language for the inductive sets, and applications….Pages 313-329
A lower bound for the formula size of rational functions….Pages 330-338
On the equivalence problem for binary DOL systems….Pages 339-347
Results on the propositional μ-calculus….Pages 348-359
An iteration theorem for simple precedence languages….Pages 360-368
The power of non-rectilinear holes….Pages 369-383
Fixed-point semantics for algebraic (tree) grammars….Pages 384-396
Completing biprefix codes….Pages 397-406
Advances in pebbling….Pages 407-417
A powerdomain for countable non-determinism….Pages 418-428
Properties of a notation for combining functions….Pages 429-441
On the power of probabilistic choice in synchronous parallel computations….Pages 442-450
Biprefix codes and semisimple algebras….Pages 451-457
Algorithmic theories of data structures….Pages 458-472
Implementation of parameterised specifications….Pages 473-488
Algebraic semantics of recursive flowchart schemes….Pages 489-501
The complexity of promise problems….Pages 502-509
Global and local invariants in transition systems….Pages 510-522
On relativization and the existence of complete sets….Pages 523-531
Semantics of interference control….Pages 532-545
Efficient simulations of multicounter machines….Pages 546-560
Event structure semantics for CCS and related languages….Pages 561-576
Domains for denotational semantics….Pages 577-610