Automata, Languages and Programming: 16th International Colloquium Stresa, Italy, July 11–15, 1989 Proceedings

Realizable and unrealizable specifications of reactive systems....Pages 1-17
Limitations of the upward separation technique (preliminary version)....Pages 18-30
Lower bounds for the low hierarchy....Pages 31-45
Efficient text searching of regular expressions....Pages 46-62
Factors of words....Pages 63-79
Asymptotically optimal distributed consensus....Pages 80-94
Time lower bounds for CREW-PRAM computation of monotone functions....Pages 95-107
Subduing self-application....Pages 108-122
Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds....Pages 123-136
Polymorphic rewriting conserves algebraic strong normalization and confluence....Pages 137-150
Completion of finite codes with finite deciphering delay....Pages 151-163
Relational semantics for recursive types and bounded quantification....Pages 164-178
A singly-exponential stratification scheme for real semi-algebraic varieties and its applications....Pages 179-193
About primitive recursive algorithms....Pages 194-206
The definability of equational graphs in monadic second-order logic....Pages 207-221
Dominoes and the regularity of DNA splicing languages....Pages 222-233
Causal trees....Pages 234-248
Infinite normal forms....Pages 249-262
On recent trends in algebraic specification....Pages 263-288
Automata with storage on infinite words....Pages 289-303
Parallel algorithmic techniques for combinatorial computation....Pages 304-318
On dice and coins: models of computation for random generation....Pages 319-340
An optimal probabilistic algorithm for synchronous Byzantine agreement....Pages 341-378
Finding triconnected components by local replacements....Pages 379-393
An improved algorithm for approximate string matching....Pages 394-404
A pointer-free data structure for merging heaps and min-max heaps....Pages 405-422
Structured operational semantics and bisimulation as a congruence....Pages 423-438
Parallel retrieval of scattered information....Pages 439-450
Tensor rank is NP-complete....Pages 451-460
The complexity of nonlinear separable optimization....Pages 461-472
General methods for the analysis of the maximum size of dynamic data structures....Pages 473-487
How to share concurrent asynchronous wait-free variables....Pages 488-505
A new approach to formal language theory by kolmogorov complexity....Pages 506-520
Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis....Pages 521-533
Completing the temporal picture....Pages 534-558
Lower bounds for computations with the floor operation....Pages 559-573
Programming, transforming, and proving with function abstractions and memories....Pages 574-588
Automata theory meets circuit complexity....Pages 589-602
Two versus one index register and modifiable versus non-modifiable programs....Pages 603-609
Shortest paths without a map....Pages 610-620
Modular system design applying graph grammars techniques....Pages 621-636
Partial communations....Pages 637-651
On the synthesis of an asynchronous reactive module....Pages 652-671
The complexity of controlled selection....Pages 672-686
Memory versus randomization in on-line algorithms....Pages 687-703
Syntactic control of interference Part 2....Pages 704-722
Characteristic formulae....Pages 723-732
A combinatorial technique for separating counting complexity classes....Pages 733-744
Horn programs and semicomputable relations on abstract structures....Pages 745-760
A note on model checking the modal v -calculus....Pages 761-772
DI-domains as information systems....Pages 773-788