Minimization

In Hopcroft's minimization algorithm [12,1] a situation arises very similar to the determinization case. In this minimization algorithm, a partition of states is repeatedly refined by considering a pair of state and symbol which might reveal that an existing subset must be split. Rather than considering a pair of state and symbol, we consider in the generalization a pair of state and `exclusive' predicate. As in the determinization algorithm we therefore need to consider all boolean combinations over the predicates present on a given state. In the actual implementation, we re-use the additional code required for the determinization algorithm in the implementation of the minimization algorithm.

The generalized minimization algorithm produces a pfsr that is minimal in the number of states. However, the pfsr is not necessarily unique, and could also be non-minimal in the number of transitions. This is caused by the fact that the predicates used in the pfsr might not be sufficiently general. For example, the language {a,b,c} can be presented with a 2-state automaton with a single transition labeled $\in\{a,b,c\}$, but e.g. also with a 2-state automaton with two transitions labeled respectively by $\in\{a,b\}$ and $\in\{c\}$. Therefore, the minimization of a pfsr includes a final cleanup step in which for each pair of states p and q all transitions from p to q with labels $\pi_1\dots \pi_i$ are combined into a single transition from p to q with associated label $\pi_1\vee\dots\vee\pi_i$. It turns out that in the case of transducers, the corresponding cleanup operator is more difficult, as we discuss in section 5.1.