Average complexity of Moore's and Hopcroft's algorithms

DOI10.1016/J.TCS.2011.10.011MaRDI QIDQ764328zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Julien David

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.10.011

zbMATH Keywords

finite automataminimization algorithmaverage complexitygeneric complexityHopcroft algorithmMoore algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms (68W40)

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 case analysis of Moore's state minimization algorithm
• Implementation and Application of Automata
• Minimisation of automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1949645 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 1418342 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Analytic combinatorics
• Around Hopcroft’s Algorithm
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Describing an algorithm by Hopcroft
• Efficient minimization of DFAs with partial transition
• Enumeration and random generation of accessible automata
• Generic-case complexity, decision problems in group theory, and random walks.
• Hopcroft’s Algorithm and Cyclic Automata
• Implementation and Application of 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

Cited in

(11)

• Average case analysis of Moore's state minimization algorithm
• Minimisation of automata
• Aggregation-based minimization of finite state automata
• On the average complexity of Moore's state minimization algorithm
• A split-based incremental deterministic automata minimization algorithm
• Hopcroft’s Algorithm and Cyclic Automata
• Re-describing an algorithm by Hopcroft
• The average complexity of Moore's state minimization algorithm is \(\mathcal O( n \log\log n)\)
• Implementation and Application of Automata
• Average case analysis of Brzozowski's algorithm
• Random deterministic automata

Describes a project that uses

Uses Software

• REGAL

This page was built for publication: Average complexity of Moore's and Hopcroft's algorithms

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