Konferenzpaper

Jahr der Veröffentlichung: 2009

Seiten: 563-580

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 20

Heftnummer: 4

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054109006747

Konferenz: 13th International Conference on Implementation and Application of Automata

Verlag: World Scientific Publishing

Abstract: 
Nondeterministic finite automata (NFAs) were introduced in [68], where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example, (i) simulation of and by several types of finite automata, (ii) minimization and approximation, (iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

Harvard-Zitierstil: Holzer, M. and Kutrib, M. (2009) NONDETERMINISTIC FINITE AUTOMATA - RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, International Journal of Foundations of Computer Science, 20(4), pp. 563-580. https://doi.org/10.1142/S0129054109006747

APA-Zitierstil: Holzer, M., & Kutrib, M. (2009). NONDETERMINISTIC FINITE AUTOMATA - RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY. International Journal of Foundations of Computer Science. 20(4), 563-580. https://doi.org/10.1142/S0129054109006747