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

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). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.

---

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). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.

---

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). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.
Content:
Front Matter....Pages -
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

---

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). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.
Content:
Front Matter....Pages -
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
....