Average case analysis of Moore's state minimization algorithm

DOI10.1007/s00453-011-9557-7zbMath1291.68176MaRDI QIDQ2429348

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

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 automata; average complexity; Moore's algorithm; state minimization algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

Diameter and stationary distribution of random \(r\)-out digraphs, Minimisation of automata, A hitchhiker's guide to descriptional complexity through analytic combinatorics, Average Case Analysis of Brzozowski's Algorithm, Random Deterministic Automata

Uses Software

• REGAL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
• Enumeration and random generation of accessible automata
• Minimisation of acyclic deterministic automata in linear time
• Re-describing an algorithm by Hopcroft
• On extremal cases of Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Linear Automaton Transformations
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Hopcroft’s Algorithm and Cyclic Automata
• The Average Complexity of Moore’s State Minimization Algorithm Is O( n loglogn)
• Efficient Minimization of DFAs with Partial Transition Functions
• The cauchy problem for the coupled maxwell and dirac equations