Average case analysis of Moore's state minimization algorithm
From MaRDI portal
Publication:2429348
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
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
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item