Hyper-Minimization in O(n 2)

DOI10.1007/978-3-540-70844-5_23MaRDI QIDQ3602817zbMATH OpenOpenAlexFDO

Authors Andrew Badr

Publication date 12 February 2009

Published in Implementation and Applications of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70844-5_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• HYPER-MINIMIZATION IN O(n²)
• Hyper-minimizing minimized deterministic finite state automata
• Hyper-minimisation Made Efficient
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton

Cites work

• A TIME AND SPACE EFFICIENT ALGORITHM FOR MINIMIZING COVER AUTOMATA FOR FINITE LANGUAGES
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 1452982 (Why is no real title available?)
• Hyper-minimizing minimized deterministic finite state automata
• Incremental construction of minimal deterministic finite cover automata
• Introduction to algorithms

Cited in

(9)

• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Better hyper-minimization. Not as fast, but fewer errors
• From equivalence to almost-equivalence, and beyond-minimizing automata with errors (extended abstract)
• Hyper-minimisation Made Efficient
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• scientific article; zbMATH DE number 7439745 (Why is no real title available?)
• Weak minimization of DFA -- an algorithm and applications

This page was built for publication: Hyper-Minimization in O(n 2)

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