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

• Autorzy: Melnikov B.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Nondeterministic Finite Automata (NFA); basic automaton; algorithms of simplification; algorithms of combining states; edge-minimization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 267--283
• Opis fizyczny: Bibliogr. 8 poz., tab., wykr.

Twórcy

autor

Melnikov B.

• Togliatti State University, Belorusskaya 14, 445667 Togliatti, Russia,

Bibliografia

• [1] B. Melnikov : Extended nondeterministic finite automata - This volume of Fundamenta Informaticae,
• [2] B. Melnikov, A. Melnikova : Edge-minimization of non-deterministic finite automata - The Korean Journal of Computational and Applied Mathematics, Vol. 8, No. 3 (2001) 469-479.
• [3] B. Melnikov, A. Melnikova : Some properties of the basis finite automaton - The Korean Journal of Computational and Applied Mathematics, Vol. 9, No. 1 (2002) 131-150.
• [4] B. Melnikov, N. Sciarini-Guryanova : Possible edges of a finite automaton defining a given regular language - The Korean Journal of Computational and Applied Mathematics, Vol. 9, No. 2 (2002) 475-485.
• [5] B. Melnikov : Discrete optimization problems - some new heuristic approaches - The 8th International Conference on High-Perfomance Computing and Grid in Asia-Pacific Region, IEEE Comp. Soc. Press Ed. (2005) 73-80.
• [6] J. Hromkovič : Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2004.
• [7] W. Brauer : Automatentheorie. Eine Einf¨uhrung in die Theorie endlicher Automaten. Teubner, 1984.
• [8] B. Melnikov, M. Sayfullina : On some algorithms of equivalent transformations for nondeterministic finite automata - Izvestiya VUZov. Matematika (Russian Department of Education Ed.), No. 2 (2009). (In Russian; English translation is expected to be published in 2009.)