Description and analysis of a bottom-up DFA minimization algorithm

DOI10.1016/j.ipl.2008.01.003zbMath1186.68242OpenAlexW2082738563MaRDI QIDQ963396

Marc Zeitoun, Jorge Almeida

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

algorithmsminimizationfinite automatonformal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

The \(\kappa\)-word problem over \(\mathsf{DRH}\) ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ A graph theoretic approach to automata minimality ⋮ The word problem for \(\omega \)-terms over DA ⋮ Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm ⋮ Minimisation of automata

Cites Work

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

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