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

Resumen

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.