On extremal cases of Hopcroft's algorithm

DOI10.1016/J.TCS.2010.05.025MaRDI QIDQ1959649zbMATH OpenOpenAlexFDO

Authors Antonio Restivo, G. Castiglione, M. Sciortino

Publication date 7 October 2010

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

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

zbMATH Keywords

deterministic finite state automataHopcroft's minimization algorithmstandard treesword trees

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
• Hopcroft’s Minimization Technique: Queues or Stacks?

Cites work

• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• A linear time solution to the single function coarsest partition problem
• Automata Studies. (AM-34)
• 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
• On Extremal Cases of Hopcroft’s Algorithm
• Re-describing an algorithm by Hopcroft
• Special factors and uniqueness conditions in rational trees
• Sturmian trees

Cited in

(27)

• Words, trees and automata minimization
• Average case analysis of Moore's state minimization algorithm
• A graph theoretic approach to automata minimality
• 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
• Morphisms and Minimisation of Weighted Automata
• Nondeterministic Moore automata and Brzozowski's minimization algorithm
• Hopcroft’s Algorithm and Cyclic Automata
• Re-describing an algorithm by Hopcroft
• Bit catastrophes for the Burrows-Wheeler transform
• Hopcroft's automaton minimization algorithm and Sturmian words
• Extension of Hoshen-Kopelman algorithm to non-lattice environments
• Around Hopcroft’s Algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• A challenging family of automata for classical minimization algorithms
• Standard Sturmian words and automata minimization algorithms
• Implementation and Application of Automata
• Nondeterministic Moore automata and Brzozowski's algorithm
• On Extremal Cases of Hopcroft’s Algorithm
• A combinatorial view on string attractors
• An extremal problem in the hypercube and optimization of asynchronous circuits
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Bit catastrophes for the Burrows-Wheeler transform
• Hopcroft's algorithm and tree-like automata
• String attractors and infinite words

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 Q1959649)