Fast brief practical DFA minimization

DOI10.1016/J.IPL.2011.12.004zbMATH Open1242.68149OpenAlexW2038358049MaRDI QIDQ437674FDOQ437674

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

Recommendations

• scientific article; zbMATH DE number 6300100
• scientific article
• 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

zbMATH Keywords

data structuresformal languagespartition refinementdeterministic finite automata

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms.
• Three Partition Refinement Algorithms
• Title not available (Why is that?)
• Re-describing an algorithm by Hopcroft
• Describing an algorithm by Hopcroft
• Simple bisimilarity minimization in \(O(m \log n)\) time
• Bisimilarity Minimization in O(m logn) Time
• Efficient minimization of DFAs with partial transition

Cited In (25)

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

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)