Hopcroft's algorithm and tree-like automata

DOI10.1051/ITA/2011011MaRDI QIDQ3006159zbMATH OpenOpenAlexFDO

Authors M. Sciortino, G. Castiglione, Antonio Restivo

Publication date 10 June 2011

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2011__45_1_59_0/, https://eudml.org/doc/222033

zbMATH Keywords

automata minimizationHopcroft's algorithmword trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On extremal cases of Hopcroft's algorithm
• On Extremal Cases of Hopcroft’s Algorithm
• Hopcroft’s Algorithm and Cyclic Automata
• On the Hopcroft's minimization technique for DFA and DFCA
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata

Cites work

• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A linear time solution to the single function coarsest partition problem
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Hopcroft’s Algorithm and Cyclic Automata
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Implementation and Application of Automata
• On Christoffel classes
• On Extremal Cases of Hopcroft’s Algorithm
• On extremal cases of Hopcroft's algorithm
• On the Hopcroft's minimization technique for DFA and DFCA
• Re-describing an algorithm by Hopcroft
• Sturmian trees

Cited in

(9)

• Circular Sturmian words and Hopcroft's algorithm
• On the Hopcroft's minimization technique for DFA and DFCA
• Nondeterministic Moore automata and Brzozowski's minimization algorithm
• Sequences of words defined by two-way transducers
• Hopcroft’s Algorithm and Cyclic Automata
• On extremal cases of Hopcroft's algorithm
• Standard Sturmian words and automata minimization algorithms
• On Extremal Cases of Hopcroft’s Algorithm
• Hopcroft’s Minimization Technique: Queues or Stacks?

This page was built for publication: Hopcroft's algorithm and tree-like automata

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