Around Hopcroft’s Algorithm

Abstract. In this paper, a reflection is made on an indeterminism inherent to Hopcroft’s minimization algorithm: the splitter choice. We have implemented two natural policies (FIFO and FILO) for managing the set of splitters for which we obtain the following practical results: the FILO strategy performs better than the FIFO strategy, in the case of a one letter alphabet, the practical complexity in the FILO case never exceeds a linear one and our implementation is more efficient than the minimization algorithm of the FSM tool. This implementation is being integrated in a finite automata library, the Dash library. Thus, we present an efficient manner to manipulate automata by using canonical minimal automata. Keywords: Finite automata, minimization, Hopcroft’s algorithm.