Once More on the Edge-Minimization of Nondeterministic Finite Automata and the Connected Problems

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. B.Melnikov@tltsu.ru

Note: [] Address for correspondence: Togliatti State University, Belorusskaya 14, 445667 Togliatti, Russia

Abstract: We consider in this paper the problem of edge-minimization for nondeterministic finite automata and some connected questions. We shall formulate a new algorithm solving this problem; this algorithm is a simplification of two ones published before. The connected problems include at first algorithms of combining states. We formulate some new sufficient conditions for the possibility of such combining.

Keywords: Nondeterministic finite automata, basic automaton, algorithms of simplification, algorithms of combining states, edge-minimization

DOI: 10.3233/FI-2010-349

Journal: Fundamenta Informaticae, vol. 104, no. 3, pp. 267-283, 2010