Average case analysis of Moore's state minimization algorithm

DOI10.1007/S00453-011-9557-7MaRDI QIDQ2429348zbMATH OpenOpenAlexFDO

Authors Frédérique Bassino, Julien David, Cyril Nicaud

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9557-7

zbMATH Keywords

finite automataaverage complexityMoore's algorithmstate minimization algorithms

Mathematics Subject Classification ID

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

Recommendations

• On the average complexity of Moore's state minimization algorithm
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)
• Average complexity of Moore's and Hopcroft's algorithms
• Average case analysis of Brzozowski's algorithm
• On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states

Cites work

• scientific article; zbMATH DE number 4039297 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 1418342 (Why is no real title available?)
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Efficient minimization of DFAs with partial transition
• Enumeration and random generation of accessible automata
• Hopcroft’s Algorithm and Cyclic Automata
• Linear Automaton Transformations
• Minimisation of acyclic deterministic automata in linear time
• On extremal cases of Hopcroft's algorithm
• On the average complexity of Moore's state minimization algorithm
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Re-describing an algorithm by Hopcroft
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)
• The cauchy problem for the coupled maxwell and dirac equations

Cited in

(9)

• Random deterministic automata
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)
• Average complexity of Moore's and Hopcroft's algorithms
• Minimisation of automata
• Diameter and stationary distribution of random \(r\)-out digraphs
• On the average complexity of Moore's state minimization algorithm
• On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Average case analysis of Brzozowski's algorithm

Describes a project that uses

Uses Software

• REGAL

This page was built for publication: Average case analysis of Moore's state minimization algorithm

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