Minimal coverings for incompletely specified sequential machines (Q1088411)

In the literature the problem of finding minimal realizations for incompletely specified machines has been treated in a number of different ways. Solutions to this problem depend on the precise definition of what minimal realization means in this case. If the behaviour of a state is defined as its related partial input-output function then the behaviour of one machine A can cover the behaviour of another machine B if it contains better defined I/O functions for all states of B. Finding a minimal covering in this case is known to be NP-complete. We develop an algebraic treatment of the problem and give a homomorphic characterization of the covering-relation. The construction of state- splitting is also characterized as a special morphism. Then a heuristic method is proposed for finding minimal coverings.