The first minimization algorithm is taken from Hopcroft and Ullman ([6]). In our implementation the following phases can be identified. Firstly, transitions are added to the incoming automaton to ensure that the transition function is total (note that it is assumed that the input is already deterministic). Then, in the second step, all pairs of non-identical states are computed. In the third phase, the automaton is adapted in such a way that states that were found to be identical receive a single name. Finally, some unneccessary transitions are thrown away (those ending and starting in the `sink' state).
The computation of the set of pairs of non-identical states starts out with pairs of states for which one element is a final state and the other element is not a final state: these clearly are non-identical. These pairs are taken as an agenda and we then proceed to find more pairs of non-identical states on the basis of these pairs. Such new non-identical pairs can be obtained by the following reasoning. If P and Q are non-identical states, and there are transitions trans(P1,Sym,P) and trans(Q1,Sym,Q) then P1, Q1 is a pair of non-identical states too.
The FSA Utilities toolbox also provides an implementation of Brzozowski's method of minimizing an automaton (Brzozowski [2], Watson [16]). In this method the (possibly non-deterministic) automaton is reversed, determinized, reversed and determinized. Note that this method is often much faster than the previous method. Moreover the input can be non-deterministic. Finally, the implementation is very simple, since it consists only of automaton reversal (a particularly simple operation) and determinization (which is useful independently).
The third algorithm for minimization that is provided is the algorithm from Hopcroft ([5]). Our implementation closely follows the presentation of Watson [16]). A disadvantage of this algorithm is that it is much more complicated than the other two.