|
There exists a linear time algorithm for the minimization of acyclic deterministic finite-state automata (ADFA) due to Dominique Revuz (Theoretical Computer Science, 181–189, 1992).
The algorithm has different phases involving the computation of a height for each state, sorting states of the same height and joining equivalent states.
We present a new linear time algorithm for the task at hand.
The algorithm is conceptionally simpler and computes the minimal automaton in only a single depth-first traversal over the automaton.
The algorithm utilizes the notion of a right-language Register known from algorithms for the incremental construction of minimal ADFAs from lists.
In an evaluation we compare the running times of both algorithms.
The results show that the new algorithm is significantly faster than Revuz' algorithm.
|
