Average complexity of Moore's and Hopcroft's algorithms

DOI10.1016/j.tcs.2011.10.011zbMath1235.68100OpenAlexW2074847588WikidataQ56830054 ScholiaQ56830054MaRDI QIDQ764328

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 automataaverage complexityminimization algorithmgeneric complexityHopcroft algorithmMoore algorithm

Mathematics Subject Classification ID

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

Related Items (5)

Random Deterministic Automata ⋮ A split-based incremental deterministic automata minimization algorithm ⋮ Aggregation-based minimization of finite state automata ⋮ Average Case Analysis of Brzozowski's Algorithm ⋮ Minimisation of automata

Uses Software

• REGAL

Cites Work

• Enumeration and random generation of accessible automata
• Minimisation of acyclic deterministic automata in linear time
• Generic-case complexity, decision problems in group theory, and random walks.
• Re-describing an algorithm by Hopcroft
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Describing an algorithm by Hopcroft
• Linear Automaton Transformations
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Hopcroft’s Algorithm and Cyclic Automata
• On Extremal Cases of Hopcroft’s Algorithm
• Efficient Minimization of DFAs with Partial Transition Functions
• Implementation and Application of Automata
• Around Hopcroft’s Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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