Scoop Minimization
Hartmut Ehrig, K.-D. Kiermeier, Hans‐Jörg Kreowski, Wolfgang Kühnel · 1974
This chapter is a continuation of the last one considering the minimization problem for initial automata in pseudo-closed categories (cf. 9.2). According to our examples in 9.9 an initial automaton in a pseudoclosed category ( K ,⊗), which is reachable and observable, is not minimal in general. Note that this implies minimality in the case of closed categories (cf. 9.5). On the other hand there are no general constructions for minimizing the number of states for initial stochastic automata for example (cf. [76]), so that we cannot expect to get such a construction for automata in pseudoclosed categories. But in most of our examples there is another construction to decrease the number of states by replacing a state by an “equivalent subset” of the remaining states. For nondeterministic automata this means that the union of the input-output functions of all the states belonging to the subset is equal to the input-output function of the given state (cf. [75]). In fact, this construction, called scoop minimization, can be formulated in the framework of automata in pseudoclosed categories and seems to be a fairly good general approximation for the construction of initial automata with a minimal number of states.