Efficient Deterministic Finite Automata Minimization Based on Backward Depth InformationReportar como inadecuado

Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons DFAs. A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity On than a naive comparison of transitions On2. Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft’s algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms.

Autor: Desheng Liu , Zhiping Huang, Yimeng Zhang, Xiaojun Guo, Shaojing Su

Fuente: http://plos.srce.hr/


Documentos relacionados