This paper investigates the nondeterministic polynomial time (NP) hard problem of producing a minimal nondeterministic finite automata (NFA). This problem is widely known to be in polynomial time (P) for deterministic finite state automata (DFA) with state equivalence methods. The authors point out that a reasonable substitute heuristic in the NFA case is to employ preorders instead of equivalence relations.

Preorders that can be used to construct the coarsest state equivalence relation (hence permitting merging), and that admit a simple recursive algorithm, are the main contribution of the paper. These preorders are ranked such that rank k involves examining transitions over state subsets of size k. The authors prove that, for an n-state NFA, their n-order preorder coincides with the basic state preorders p q if every string taking the start state to p also takes the start state to q, and p q if every word that can take p to a final state can take q to a final state.

Champarnaud and Coulon also present some experimental studies on the efficacy of their first-order method, but comment that randomly generated NFA may be unrepresentative of NFA encountered in practice. Perhaps some of the newer methods for generating random samples of graphs with prescribed constraints may be useful in subsequent experimental studies of their method.