Extended Nondeterministic Finite Automata

Issue title: Hardest Boolean Functions and O.B. Lupanov

Article type: Research Article

Authors: Melnikov, Boris

Affiliations: Faculty of Mathematics and Informatics, Togliatti State University, Togliatti, Russia. [email protected]

Note: [] Thanks for the help to Prof. Dr. Juraj Hromkovič. Address for correspondence: Faculty of Mathematics and Informatics, Togliatti State University, Belorusskaya 14, 445667 Togliatti, Russia

Abstract: We consider a new expansion of nondeterministic finite automata. The goals of this consideration are: to apply some algorithms of such expansion for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; using such automata, we often can simplify some proofs for algorithms of simplification of usual nondeterministic automata.

Keywords: Nondeterministic finite automata, extended automata, basic automaton, algorithms of simplification

DOI: 10.3233/FI-2010-348

Journal: Fundamenta Informaticae, vol. 104, no. 3, pp. 255-265, 2010