Average complexity of Moore's and Hopcroft's algorithms

DOI10.1016/J.TCS.2011.10.011zbMATH Open1235.68100DBLPjournals/tcs/David12OpenAlexW2074847588WikidataQ56830054 ScholiaQ56830054MaRDI QIDQ764328FDOQ764328

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

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

zbMATH Keywords

finite automataminimization algorithmaverage complexitygeneric complexityHopcroft algorithmMoore algorithm

Mathematics Subject Classification ID

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

Cites Work

• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Analytic combinatorics
• Title not available (Why is that?)
• 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?)
• Title not available (Why is that?)
• Enumeration and random generation of accessible automata
• Generic-case complexity, decision problems in group theory, and random walks.
• On the average complexity of Moore's state minimization algorithm
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Re-describing an algorithm by Hopcroft
• Implementation and Application of Automata
• Describing an algorithm by Hopcroft
• Efficient minimization of DFAs with partial transition
• Minimisation of acyclic deterministic automata in linear time
• Linear Automaton Transformations
• Hopcroft’s Algorithm and Cyclic Automata
• On Extremal Cases of Hopcroft’s Algorithm
• Title not available (Why is that?)
• Around Hopcroft’s Algorithm

Cited In (11)

• Average case analysis of Moore's state minimization algorithm
• Minimisation of automata
• On the average complexity of Moore's state minimization algorithm
• Aggregation-based minimization of finite state automata
• 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

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)