





Technical Report: DCC200703On the performance of automata minimization algorithmsMarco Almeida, Nelma Moreira and Rogério ReisDCCFC & LIACC, Universidade do PortoR. do Campo Alegre 1021/1055 , 4169007 Porto, Portugal Phone: +351 220402926 , Fax: 351 22 402 950 Email: {mfa, nam,rvr}@ncc.up.pt AbstractThere are several well known algorithms to minimize deterministic finite automata. Apart from the theoretical worstcase running time analysis, however, not much is known about the averagecase analysis or practical performance of each of these algorithms. On this paper we compare three minimization algorithms based on experimental results. The choice of the algorithms was based on the fact that although having different worstcase complexities they are usually considered to be ones that achieve best performance. We used an uniform random generator of (initiallyconnected) deterministic finite automata for the input data, and thus our results are statistically accurate. Because one of the algorithms allowed to minimize nondeterministic finite automata (NFA), we also developed a nonuniform random generator for NFAs. Nevertheless, although not statistically significant, the results in this case are fairly interesting. 

