A polynomial double reversal minimization algorithm for deterministic finite automata

DOI10.1016/J.TCS.2013.03.005MaRDI QIDQ386994zbMATH OpenOpenAlexWikidataFDO

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

Publication date 11 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.03.005

zbMATH Keywords

atomic automataDFA minimizationpolynomial double reversal algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• DFA minimization: double reversal versus split minimization algorithms
• scientific article; zbMATH DE number 4108165
• Brzozowski's minimization algorithm -- more robust than expected (extended abstract)
• Fast brief practical DFA minimization
• Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm

Cites work

• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Learning regular languages using RFSAs.
• MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON
• The universal automaton
• Theory of átomata

Cited in

(8)

• DFA minimization: double reversal versus split minimization algorithms
• Theory of átomata
• Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm
• Standard Sturmian words and automata minimization algorithms
• A congruence-based perspective on automata minimization algorithms
• Brzozowski algorithm is generically super-polynomial for deterministic automata
• Approximate state reduction of fuzzy finite automata
• Polynomial crisp-minimization algorithm for fuzzy deterministic automata

Describes a project that uses

Uses Software

• RFSA

This page was built for publication: A polynomial double reversal minimization algorithm for deterministic finite automata

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