Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information.

Area of Science:

• Theoretical Computer Science
• Automata Theory
• Algorithm Design

Background:

• Minimizing deterministic finite automatons (DFAs) is crucial for efficient computation and implementation.
• Existing minimization algorithms may have limitations in terms of time complexity or applicability to complex automaton structures.

Purpose of the Study:

• To present a new, efficient, and generalizable algorithm for DFA minimization.
• To reduce the time complexity of DFA minimization while enhancing its applicability to diverse automaton types.

Main Methods:

• The algorithm employs a two-phase approach: backward depth information construction for initial state partitioning, followed by hash table-based refinement.
• Backward depth information is utilized to create coarse partitions, reducing the need for extensive refinement.

Main Results:

• The proposed algorithm achieves a linear time complexity of O(n), significantly outperforming the O(n^2) complexity of naive transition comparison.
• Experimental comparisons show the algorithm runs faster than traditional methods, including Hopcroft's algorithm.
• The method demonstrates greater generality, applicable to acyclic, simple cyclic, and complex cyclic DFAs.

Conclusions:

• The developed DFA minimization algorithm offers lower time complexity, enhanced generality, and scalability.
• This approach provides a more efficient and versatile solution for minimizing deterministic finite automatons.