This volume contains the proceedings of ICALP 89, held at Stresa, Italy, July 11-15, 1989. ICALP 89 is the 16th International Colloquium on Automata, Languages and Programming in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS).

Realizable and unrealizable specifications of reactive systems.- Limitations of the upward separation technique (preliminary version).- Lower bounds for the low hierarchy.- Efficient text searching of regular expressions.- Factors of words.- Asymptotically optimal distributed consensus.- Time lower bounds for CREW-PRAM computation of monotone functions.- Subduing self-application.- Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds.- Polymorphic rewriting conserves algebraic strong normalization and confluence.- Completion of finite codes with finite deciphering delay.- Relational semantics for recursive types and bounded quantification.- A singly-exponential stratification scheme for real semi-algebraic varieties and its applications.- About primitive recursive algorithms.- The definability of equational graphs in monadic second-order logic.- Dominoes and the regularity of DNA splicing languages.- Causal trees.- Infinite normal forms.- On recent trends in algebraic specification.- Automata with storage on infinite words.- Parallel algorithmic techniques for combinatorial computation.- On dice and coins: models of computation for random generation.- An optimal probabilistic algorithm for synchronous Byzantine agreement.- Finding triconnected components by local replacements.- An improved algorithm for approximate string matching.- A pointer-free data structure for merging heaps and min-max heaps.- Structured operational semantics and bisimulation as a congruence.- Parallel retrieval of scattered information.- Tensor rank is NP-complete.- The complexity of nonlinear separable optimization.- General methods for the analysis of the maximum size of dynamic data structures.- How to share concurrent asynchronous wait-free variables.- A newapproach to formal language theory by kolmogorov complexity.- Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis.- Completing the temporal picture.- Lower bounds for computations with the floor operation.- Programming, transforming, and proving with function abstractions and memories.- Automata theory meets circuit complexity.- Two versus one index register and modifiable versus non-modifiable programs.- Shortest paths without a map.- Modular system design applying graph grammars techniques.- Partial communations.- On the synthesis of an asynchronous reactive module.- The complexity of controlled selection.- Memory versus randomization in on-line algorithms.- Syntactic control of interference Part 2.- Characteristic formulae.- A combinatorial technique for separating counting complexity classes.- Horn programs and semicomputable relations on abstract structures.- A note on model checking the modal v-calculus.- DI-domains as information systems.