Average complexity of Moore’s and Hopcroft’s algorithms

2011/11/05 by Julien David · 8 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Algorithm #Alphabet #Automaton #Computer science #Discrete mathematics #Implementation #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Minification #State (computer science) #Theoretical computer science #semigroups and automata theory

paper · doi:10.1016/j.tcs.2011.10.011

published in Theoretical Computer Science 417, 50-65 (Elsevier BV)

openalex publication_date 2011/11/05 · crossref created 2011/11/05 · crossref issued 2012/02/01 · crossref published 2012/02/01 · crossref published-print 2012/02/01 · crossref deposited 2019/06/19 · crossref indexed 2024/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• Generic-case complexity, decision problems in group theory, and random walks
• Minimisation of acyclic deterministic automata in linear time
• Linear automaton transformations
• Re-describing an algorithm by Hopcroft

Cited by

• DFA minimization [wikipedia]