Automata, Languages and Programming

1. Front Matter

   PDF

2. Realizable and unrealizable specifications of reactive systems

   • Martín Abadi, Leslie Lamport, Pierre Wolper

   Pages 1-17

3. Limitations of the upward separation technique (preliminary version)

   • Eric Allender

   Pages 18-30

4. Lower bounds for the low hierarchy

   • Eric Allender, Lane A. Hemachandra

   Pages 31-45

5. Efficient text searching of regular expressions

   • Ricardo A. Baeza-Yates, Gaston H. Gonnet

   Pages 46-62

6. Factors of words

   • Danièle Beauquier, Jean-Eric Pin

   Pages 63-79

7. Asymptotically optimal distributed consensus

   • Piotr Berman, Juan A. Garay

   Pages 80-94

8. Time lower bounds for CREW-PRAM computation of monotone functions

   • Gianfranco Bilardi, Abha Moitra

   Pages 95-107

9. Subduing self-application

   • Corrado Böhm

   Pages 108-122

10. Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds

    • Gilles Brassard, Claude Crépeau, Moti Yung

    Pages 123-136

11. Polymorphic rewriting conserves algebraic strong normalization and confluence

    • Val Breazu-Tannen, Jean Gallier

    Pages 137-150

12. Completion of finite codes with finite deciphering delay

    • Véronique Bruyere

    Pages 151-163

13. Relational semantics for recursive types and bounded quantification

    • Felice Cardone

    Pages 164-178

14. A singly-exponential stratification scheme for real semi-algebraic varieties and its applications

    • Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

    Pages 179-193

15. About primitive recursive algorithms

    • Loïc Colson

    Pages 194-206

16. The definability of equational graphs in monadic second-order logic

    • B. Courcelle

    Pages 207-221

17. Dominoes and the regularity of DNA splicing languages

    • Karel Culik II, Tero Harju

    Pages 222-233

18. Causal trees

    • Ph. Darondeau, P. Degano

    Pages 234-248

19. Infinite normal forms

    • Nachum Dershowitz, Stéphane Kaplan, David A. Plaisted

    Pages 249-262

20. On recent trends in algebraic specification

    • H. Ehrig, P. Pepper, F. Orejas

    Pages 263-288

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.

• Automat
• Graph
• algorithms
• automata
• automata theory
• complexity
• computability
• concurrency
• formal language
• linear optimization
• logic
• programming language
• theorem proving
• theoretical computer science
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics