Konferenzpaper

Jahr der Veröffentlichung: 2011

Seiten: 456-470

Zeitschrift: Information and Computation

Bandnummer: 209

Heftnummer: 3

ISSN: 0890-5401

DOI Link: https://doi.org/10.1016/j.ic.2010.11.013

Konferenz: 3rd International Conference on Language and Automata Theory and Applications

Verlag: Elsevier

Abstract: 
Finite automata are probably best known for being equivalent to right-linear context-free grammars and, thus, for capturing the lowest level of the Chomsky-hierarchy, the family of regular languages. Over the last half century, a vast literature documenting the importance of deterministic, nondeterministic, and alternating finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss developments relevant to finite automata related problems like. for example, (i) simulation of and by several types of finite automata, (ii) standard automata problems such as fixed and general membership, emptiness, universality, equivalence, and related problems, and (iii) minimization and approximation. We thus come across descriptional and computational complexity issues of finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved. (C) 2010 Elsevier Inc. All rights reserved.

Harvard-Zitierstil: Holzer, M. and Kutrib, M. (2011) Descriptional and computational complexity of finite automata-A survey, Information and computation, 209(3), pp. 456-470. https://doi.org/10.1016/j.ic.2010.11.013

APA-Zitierstil: Holzer, M., & Kutrib, M. (2011). Descriptional and computational complexity of finite automata-A survey. Information and computation. 209(3), 456-470. https://doi.org/10.1016/j.ic.2010.11.013