An approach to algorithmizing the problem of vertex minimization of nondeterministic automata. Part I. Problem statement and the brief description of the basis methods
Mikhail Abramyan, Boris Feliksovich Melnikov · IOP Conference Series Materials Science and Engineering · 2020
Abstract We consider our approach to the problem of vertex minimization of nondeterministic finite automata. It comes down to constructing a lot of grids and knocking out on its basis an optimal (or pseudo-optimal) subset. However, our problem is much more complicated than the classical problem of optimal coverage of a set, since we need to succeed (to build pseudo-optimal solutions in an acceptable time) in its particular case; in this particular case, we are considering has many specific features, which are not characteristic of most other variants of the problem of optimal coverage of a set. In the first part of the paper, we consider issues related to the brief description of the basic branch-and-bound method, testing approach to the basic method, and some modifications the basic algorithm.