Champarnaud and Coulon deal with the problem of reducing the number of states of a given nondeterministic finite automaton (NFA) A. For deterministic automata, it is well known that the number of states can actually be minimized in polynomial time: two states can be merged into a single one if they belong to the same equivalence class under the Nerode equivalence ≡, which can be computed efficiently. In the case of NFAs, two preorderings ⊆l and ⊆r take over the role of ≡; p ⊆l q (p ⊆r q) means that the left (right) language corresponding to state p is contained in the one corresponding to ~q. However, the computation of these relations is nondeterministic polynomial time (NP) hard, as is the state minimization problem itself.
This paper presents an approximation algorithm, based on using stronger relations ⊆l1, ⊆r1 in place of ⊆l, ⊆r. In this way, the time complexity is reduced to O(mn), where n is the number of states and m the number of transitions. There is actually a hierarchy of relations ⊆lk, ⊆rk; using them for higher k yields better approximations for the desired minimal NFA, at the cost of increased complexity. The complexity is still polynomial for any fixed k.
The original version of this paper is incorrect, since it was based on a faulty, insufficient condition for merging two states. A correction is given in a later issue of the journal [1]. It contains a counterexample and describes how other results and the state minimization algorithm have to be modified.
