Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information

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...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2016-11, Vol.11 (11), p.e0165864-e0165864
Main Authors: Liu, Desheng, Huang, Zhiping, Zhang, Yimeng, Guo, Xiaojun, Su, Shaojing
Format: Article
Language:English
Subjects:
Algorithms
Automata theory
Automation
Comparative analysis
Complexity
Computational Biology - methods
Computer and Information Sciences
Computer science
Construction methods
Efficiency
Engineering and Technology
Finite Element Analysis
Grammar
Hash based algorithms
International conferences
Mathematical problems
Optimization
Physical Sciences
Research and Analysis Methods
Social Sciences
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 O(n) than a naive comparison of transitions O(n2). 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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0165864