On Extremal Cases of Hopcroft’s Algorithm

DOI10.1007/978-3-642-02979-0_5MaRDI QIDQ3637337zbMATH OpenOpenAlexFDO

Authors M. Sciortino, G. Castiglione, Antonio Restivo

Publication date 9 July 2009

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02979-0_5

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On extremal cases of Hopcroft's algorithm
• Hopcroft's algorithm and tree-like automata
• Hopcroft’s Algorithm and Cyclic Automata
• On the Hopcroft's minimization technique for DFA and DFCA
• Minimisation of automata

Cites work

• A linear time solution to the single function coarsest partition problem
• Circular Sturmian words and Hopcroft's algorithm
• Codes and equations on trees
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Hopcroft’s Algorithm and Cyclic Automata
• Implementation and Application of Automata
• On Christoffel classes
• Re-describing an algorithm by Hopcroft
• Special factors and uniqueness conditions in rational trees
• Sturmian trees

Cited in

(17)

• Words, trees and automata minimization
• A tight analysis and near-optimal instances of the algorithm of Anderson and Woll
• On the Hopcroft's minimization technique for DFA and DFCA
• Epichristoffel Words and Minimization of Moore Automata
• Minimisation of automata
• Hopcroft’s Algorithm and Cyclic Automata
• Hopcroft's automaton minimization algorithm and Sturmian words
• On extremal cases of Hopcroft's algorithm
• Extension of Hoshen-Kopelman algorithm to non-lattice environments
• Average complexity of Moore's and Hopcroft's algorithms
• Around Hopcroft’s Algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• A challenging family of automata for classical minimization algorithms
• Implementation and Application of Automata
• An extremal problem in the hypercube and optimization of asynchronous circuits
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Hopcroft's algorithm and tree-like automata

Describes a project that uses

Uses Software

• AMoRE

This page was built for publication: On Extremal Cases of Hopcroft’s Algorithm

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