The State Minimization Problem for Nondeterministic Finite Automata: The Parallel Implementation of the Truncated Branch and Bound Method
Boris Feliksovich Melnikov, Andrey Vladimirovich Tsyganov · 2012
In this paper we present an approach to the parallel implementation of the state minimization problem for nondeterministic finite automata. This approach is based on the truncated branch and bound method and also on the usage of basis andCOMautomata for the given language. Minimum state automata are searched as sub-automata of theCOMautomaton. Some sufficient conditions for their equivalence to the given nondeterministic automaton are proved in terms of the loops of the basis automaton. We suggest exact and heuristic state minimization algorithms, discuss their implementation details and provide some experimental results.