Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 2

available in:   PDF (466 kB) PS (251 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-02-0193


Descriptional Complexity of Machines with Limited Resources

Jonathan Goldstine (Department of Computer Science Pennsylvania State University, USA)

Martin Kappes (Avaya Labs, USA)

Chandra M.R. Kintala (Avaya Labs, USA)

Hing Leung (Department of Computer Science, New Mexico State University, USA)

Andreas Malcher (Department of Computer Science, University of Frankfurt, Germany)

Detlef Wotschke (Department of Computer Science, University of Frankfurt, Germany)

Abstract: Over the last 30 years or so many results have appeared on the descriptional complexity of machines with limited resources. Since these results have appeared in a variety of different contexts, our goal here is to provide a survey of these results. Particular emphasis is put on limiting resources (e.g., nondeterminism, ambiguity, lookahead, etc.) for various types of finite state machines, pushdown automata, parsers and cellular automata and on the effect it has on their descriptional complexity. We also address the question of how descriptional complexity might help in the future to solve practical issues, such as software reliability.

1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut J├╝rgensen.

Keywords: ambiguity, cellular automata, descriptional complexity, finite automata, formal languages, nondeterminism, parsers, pushdown automata, software reliability

Categories: F.1, F.4