Computing the weight of subtasks in state minimization of nondeterministic finite automata by the branch and bound method

Abstract

Background. The study considers various aspects of constructing iterative anytime algorithms for solving the problem of state minimization of nondeterministic finite automata. Although this problem was posed back in the 60s of the 20th century, it is NP-hard; therefore, the development of efficient algorithms for its solution remains a relevant problem. The purpose of the study is to analysis of the choice influence of different variants of subproblems’ weight characteristics using branch and bound method on the efficiency of the basic algorithm version and its modifications, using various heuristics. Materials and methods. The study is based on the analysis of numerical experiments performed using the software implementation of the described algorithms. The program is implemented in C# 6.0 for the .NET Framework. Results. The results are the revealed patterns associated with the choice of the weight characteristics of subtasks in the branch and bound method for the algorithm of the nondeterministic finite automata state minimization. Conclusions. We determine optimal weight characteristics both for the basic algorithm and for its modifications supplied with additional heuristics. We also show that the use of these weight characteristics together with additional heuristics can significantly increase efficiency of the developed algorithms.

Keywords

• nondeterministic finite automata
• minimization
• branch and bound method
• heuristic algorithm
• implementation