Description and analysis of a bottom-up DFA minimization algorithm

DOI10.1016/J.IPL.2008.01.003MaRDI QIDQ963396zbMATH OpenOpenAlexFDO

Authors Jorge Almeida, Marc Zeitoun

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.01.003

zbMATH Keywords

algorithmsminimizationformal languagesfinite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Fast brief practical DFA minimization
• scientific article; zbMATH DE number 6300100
• Incremental DFA minimisation
• Incremental DFA minimisation
• OPTIMAL HYPER-MINIMIZATION

Cites work

• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• A new algorithm for the construction of minimal acyclic DFAs.
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Depth-First Search and Linear Graph Algorithms
• Describing an algorithm by Hopcroft
• Fast canonization of circular strings
• Incremental Construction and Maintenance of Minimal Finite-State Automata
• Introduction to algorithms
• Lexicographically least circular substrings
• Minimisation of acyclic deterministic automata in linear time
• Re-describing an algorithm by Hopcroft
• THE EQUATIONAL THEORY OF ω-TERMS FOR FINITE ${\mathcal R}$-TRIVIAL SEMIGROUPS

Cited in

(16)

• Some New Features and Algorithms for the Study of DFA
• A graph theoretic approach to automata minimality
• scientific article; zbMATH DE number 1955813 (Why is no real title available?)
• Weak minimization of DFA -- an algorithm and applications
• Quantum algorithm for lexicographically minimal string rotation
• Fast brief practical DFA minimization
• Minimisation of automata
• Once more on the edge-minimization of nondeterministic finite automata and the connected problems
• The \(\kappa\)-word problem over \(\mathsf{DRH}\)
• A new algorithm for the construction of minimal acyclic DFAs.
• Efficient algorithms for the inference of minimum size DFAs
• The word problem for \(\omega \)-terms over DA
• Finding All Minimum-Size DFA Consistent with Given Examples: SAT-Based Approach
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Weak Minimization of DFA — An Algorithm and Applications
• Cycle-aware minimization of acyclic deterministic finite-state automata

This page was built for publication: Description and analysis of a bottom-up DFA minimization algorithm

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