Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm

DOI10.1142/S0129054114500282MaRDI QIDQ2941086zbMATH OpenWikidataFDO

Authors Pedro García, Damián López, Manuel Vázquez de Parga

Publication date 21 January 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054114500282

zbMATH Keywords

Brzozowski's algorithmDFA minimizationHopcroft's algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• DFA minimization: double reversal versus split minimization algorithms
• A split-based incremental deterministic automata minimization algorithm
• scientific article; zbMATH DE number 6300100
• Brzozowski's minimization algorithm -- more robust than expected (extended abstract)
• Fast brief practical DFA minimization

Cites work

• A geometrical view of the determinization and minimization of finite-state automata
• A polynomial double reversal minimization algorithm for deterministic finite automata
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
• Describing an algorithm by Hopcroft
• MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON
• Re-describing an algorithm by Hopcroft

Cited in

(6)

• DFA minimization: double reversal versus split minimization algorithms
• A polynomial double reversal minimization algorithm for deterministic finite automata
• Standard Sturmian words and automata minimization algorithms
• Brzozowski's minimization algorithm -- more robust than expected (extended abstract)
• Approximate state reduction of fuzzy finite automata
• A split-based incremental deterministic automata minimization algorithm

This page was built for publication: Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941086)