JUCS - Journal of Universal Computer Science 8(2): 193-234, doi: 10.3217/jucs-008-02-0193
Descriptional Complexity of Machines with Limited Resources
Jonathan Goldstine‡, Martin Kappes§, Chandra M.R. Kintala§, Hing Leung|, Andreas Malcher¶, Detlef Wotschke¶‡ Department of Computer Science Pennsylvania State University, United States of America§ Avaya Labs, Basking Ridge, NJ, United States of America| Department of Computer Science, New Mexico State University, United States of America¶ Department of Computer Science, University of Frankfurt, Germany
Corresponding author: Jonathan Goldstine ( goldstin@cse.psu.edu ) © Jonathan Goldstine, Martin Kappes, Chandra Kintala, Hing Leung, Andreas Malcher, Detlef Wotschke. This article is freely available under the J.UCS Open Content License. Citation:
Goldstine J, Kappes M, Kintala CM.R, Leung H, Malcher A, Wotschke D (2002) Descriptional Complexity of Machines with Limited Resources. JUCS - Journal of Universal Computer Science 8(2): 193-234. https://doi.org/10.3217/jucs-008-02-0193 |  |
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
descriptional complexity, nondeterminism, ambiguity, formal languages, finite automata, pushdown automata, parsers, cellular automata, software reliability