Fast brief practical DFA minimization

DOI10.1016/J.IPL.2011.12.004MaRDI QIDQ437674zbMATH OpenOpenAlexFDO

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 structuresdeterministic finite automataformal languagespartition refinement

Mathematics Subject Classification ID

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

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

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

Cited in

(27)

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

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)