Average case analysis of Moore's state minimization algorithm

DOI10.1007/S00453-011-9557-7zbMATH Open1291.68176OpenAlexW2088285637MaRDI QIDQ2429348FDOQ2429348

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

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

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)

Cites Work

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

Cited In (9)

• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Minimisation of automata
• 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
• Diameter and stationary distribution of random \(r\)-out digraphs
• 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
• Random deterministic automata

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)