Minimization of Acyclic DFAs
Johannes Bubenzer · 2011
Abstract. There exists a linear time algorithm for the minimization of acyclic deter-ministic finite-state automata (ADFA) due to Dominique Revuz [17]. 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 al-gorithm 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 com-pare the running times of both algorithms. The results show that the new algorithm is significantly faster than Revuz ’ algorithm.