Conference paper

Publication year: 2009

Pages: 563-580

Journal: International Journal of Foundations of Computer Science

Volume number: 20

Issue number: 4

ISSN: 0129-0541

eISSN: 1793-6373

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

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

Publisher: 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 Citation style: 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 Citation style: 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