Average complexity of Moore's and Hopcroft's algorithms

DOI10.1016/j.tcs.2011.10.011zbMath1235.68100WikidataQ56830054 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 automata; average complexity; minimization algorithm; generic complexity; Hopcroft algorithm; Moore algorithm

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68Q45: Formal languages and automata

Related Items

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

Uses Software

• REGAL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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