Fast brief practical DFA minimization

DOI10.1016/J.IPL.2011.12.004MaRDI QIDQ437674zbMATHOpenAlexFDO

Authors Antti Valmari

Publication date 18 July 2012

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

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

zbMATH Keywords

data structuresformal languagespartition refinementdeterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05)

Recommendations

• scientific article; zbMATH DE number 6300100
• scientific article; zbMATH DE number 4166871
• Description and analysis of a bottom-up DFA minimization algorithm
• scientific article; zbMATH DE number 4108165
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata

Cites work

• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• Bisimilarity Minimization in O(m logn) Time
• Describing an algorithm by Hopcroft
• Efficient minimization of DFAs with partial transition
• Introduction to algorithms.
• Re-describing an algorithm by Hopcroft
• Simple bisimilarity minimization in \(O(m \log n)\) time
• Three Partition Refinement Algorithms

Cited in

(25)

• Incremental DFA minimisation
• scientific article; zbMATH DE number 3874624 (Why is no real title available?)
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Minimization of syntax diagrams with multiport components
• Cycle-aware minimization of acyclic deterministic finite-state automata
• Description and analysis of a bottom-up DFA minimization algorithm
• Efficient minimization of deterministic weak \(\omega\)-automata
• Minimisation of automata
• Efficient minimization of DFAs with partial transition
• Efficient algorithms for the inference of minimum size DFAs
• Five Determinisation Algorithms
• A note on mc-DFA and its minimization
• Fixing the state budget: approximation of regular languages with small DFAs
• Some remarks on automata minimality
• Incremental DFA minimisation
• A polynomial double reversal minimization algorithm for deterministic finite automata
• Weak Minimization of DFA — An Algorithm and Applications
• DFA minimization: double reversal versus split minimization algorithms
• From tree automata to string automata minimization
• A geometrical view of the determinization and minimization of finite-state automata
• A minimized automaton representation of reachable states
• Realization of finite-automaton algorithms by structured programs. II
• Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm
• scientific article; zbMATH DE number 1955813 (Why is no real title available?)
• scientific article; zbMATH DE number 4166871 (Why is no real title available?)

This page was built for publication: Fast brief practical DFA minimization

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