The Best Nondeterministic Representations of Finite Orderings

摘要

This paper formally presents an algorithm to compute the nondeterministic realization with the least number of states that represents an order relation. For this purpose, each input order relation is considered as a finite automaton in a straightforward way. Then the automaton is subject to an iterative reduction process where the main tool for removing states is scoop minimization. So states whose role can be accomplished by a set of other states can be skipped. Moreover, we can create new states to allow further scoop reductions. The algorithm can be configured by the user to bound its performance to polynomial time.