Automata, Languages, and Programming

1. Front Matter

   PDF

2. Unexpected upper bounds on the complexity of some communication games

   • Pavel Pudlák

   Pages 1-10

3. Valuations and unambiguity of languages, with applications to fractal geometry

   • Henning Fernau, Ludwig Staiger

   Pages 11-22

4. On the computational power of probabilistic and faulty neural networks

   • Hava T. Siegelmann

   Pages 23-34

5. Deciding properties of integral relational automata

   • Kārlis Čerāns

   Pages 35-46

6. On the cost of recomputing: tight bounds on pebbling with faults

   • Yonatan Aumann, Judit Bar-Ilan, Uriel Feige

   Pages 47-58

7. On some relations between dynamical systems and transition systems

   • Eugene Asarin, Oded Maler

   Pages 59-72

8. Complexity results for multi-pebble automata and their logics

   • Noa Globerman, David Harel

   Pages 73-82

9. An analysis of the Core-ML language: Expressive power and type reconstruction

   • Paris C. Kanellakis, Gerd G. Hillebrand, Harry G. Mairson

   Pages 83-105

10. Expressiveness of efficient semi-deterministic choice constructs

    • Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht

    Pages 106-117

11. Tailoring recursion for complexity

    • Erich Grädel, Yuri Gurevich

    Pages 118-129

12. Determinizing asynchronous automata

    • Nils Klarlund, Madhavan Mukund, Milind Sohoni

    Pages 130-141

13. On the complementation of Büchi asynchronous cellular automata

    • Anca Muscholl

    Pages 142-153

14. Distribution and locality of concurrent systems

    • Flavio Corradini, Rocco De Nicola

    Pages 154-165

15. Liveness in timed and untimed systems

    • Rainer Gawlick, Roberto Segala, Jørgen Søgaard-Andersen, Nancy Lynch

    Pages 166-177

16. Average-case analysis of pattern-matching in trees under the BST probability model

    • José -Ramón Sánchez-Couso, María -Inés Fernández-Camacho

    Pages 178-190

17. On the approximation of shortest common supersequences and longest common subsequences

    • Tao Jiang, Ming Li

    Pages 191-202

18. Optimal parallel algorithms for Prefix Matching

    • Ramesh Hariharan, S. Muthukrishnan

    Pages 203-214

19. Optimal two-dimensional compressed matching

    • Amihood Amir, Gary Benson, Martin Farach

    Pages 215-226

20. Maintaining spanning trees of small diameter

    • Giuseppe F. Italiano, Rajiv Ramaswami

    Pages 227-238

This volume constitutes the proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP 94), held at Jerusalem in July 1994. ICALP is an annual conference sponsored by the European Association on Theoretical Computer Science (EATCS). The proceedings contains 48 refereed papers selected from 154 submissions and 4 invited papers. The papers cover the whole range of theoretical computer science; they are organized in sections on theory of computation, automata and computation models, expressive power, automata and concurrency, pattern matching, data structures, computational complexity, logic and verification, formal languages, term rewriting, algorithms and communications, graph algorithms, randomized complexity, various algorithms.

• Automat
• algorithm
• algorithms
• automata
• complexity
• computer
• computer science
• data structure
• data structures
• formal language
• formal languages
• logic
• programming
• term rewriting
• verification
• algorithm analysis and problem complexity

Policies and ethics