Description and analysis of a bottom-up DFA minimization algorithm

DOI10.1016/J.IPL.2008.01.003zbMATH Open1186.68242OpenAlexW2082738563MaRDI QIDQ963396FDOQ963396

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

Recommendations

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

zbMATH Keywords

algorithmsminimizationformal languagesfinite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (16)

• Title not available (Why is that?)
• Quantum algorithm for lexicographically minimal string rotation
• A graph theoretic approach to automata minimality
• Weak minimization of DFA -- an algorithm and applications
• 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
• Some New Features and Algorithms for the Study of DFA

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)