On the application of some heuristics in the study of the state minimization problem for nondeterministic finite automata by the branch and bound method. Part 1

Mikhail Abramyan, Boris Melnikov


We consider the problem of state minimization of nondeterministic finite automata. One of the ways to solve it is to analyze a subset of the set of states of two canonical automa-ta constructed on the basis of the initial nondeterministic finite automaton. In this case, the most difficult stage of the solution is to find the minimum cover of the auxiliary logical matrix by special subsets of its elements with a value of 1 (true). If some additional conditions are satisfied, then using the found mini-mum cover makes it possible to construct a finite automaton that is equivalent to the initial one and has the minimum num-ber of states. We describe a basic algorithm for finding the minimum cov-er based on the branch and bound method and additional heu-ristics that can be combined with this basic algorithm. All the algorithms under consideration are iterative anytime algo-rithms that yield the best current-step quasi-optimal solution at any time. The algorithms are implemented in C# 6.0 for the .NET Framework. The results of numerical experiments are presented that demonstrate the comparative efficiency of the described algorithms.

Full Text:

PDF (Russian)


Abramyan M.E., Melnikov B.F. Investigation of the problem of state minimization of nondeterministic finite automata using the branch and bound method // Cloud of Science. 2020. Vol. 7, No. 2 P. 297–319 (in Russian.

Abramyan M.E. On one approach to the implementation of the branch and bound method for optimization problems // Information approaches in modeling and control: approaches, methods, solutions. Collection of scientific papers of the II Russian scientific conference with international participation. Part 1. Tolyatti, 2019. P. 56–64 (in Russian.

Aho A., Ullman J. The theory of parsing, translation, and compiling. Vol. 1. – M. : Mir Publ, 1978 (in Russian.

Jiang T., Ravikumar B. Minimal NFA problems are hard // SIAM J. Comput. 1993. Vol. 22. No. 6. P. 1117–1141.

Melnikov B.F. Multiheuristic approach to discrete optimization prob-lems // Cybernetics and Systems Analysis. 2006. Vol. 42. No. 3. P. 335–341.

Melnikov B.F., Melnikova E.A., Pivneva S.V., Dudnikov V.A., Davydova E.V. Geometric and game approaches for some discrete optimization problems // CEUR Workshop Proceedings. 2018. Vol. 2212. P. 312–321.

Melnikov B. Once more on the edge-minimization of nondeterminis-tic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol. 104. No. 3. P. 267–283.

Melnikov B.F. Regular languages and nondeterministic finite autom-ata: a monograph. – M. : RGSU Publ., 2018 (in Russian.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. 2017. Vol. 5. No. 10. P. 9–17.


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162