Skip to main content
SpringerLink
Log in
Book cover

Automata, Languages, and Programming

21st International Colloquium, ICALP '94, Jerusalem, Israel, July 11-14, 1994. Proceedings

  • Conference proceedings
  • © 1994

Overview

Editors:
  1. Serge Abiteboul
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Eli Shamir
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 820)

Included in the following conference series:

Conference proceedings info: ICALP 1994.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (52 papers)

  1. Front Matter

    Download chapter 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
Back to top

Other volumes

  1. Automata, Languages and Programming

Keywords

About this book

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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation