On extremal cases of Hopcroft's algorithm

DOI10.1016/j.tcs.2010.05.025zbMath1214.68193OpenAlexW2000520861MaRDI QIDQ1959649

Antonio Restivo, Giuseppa Castiglione, Marinella 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)

Related Items (11)

Morphisms and Minimisation of Weighted Automata ⋮ Bit catastrophes for the Burrows-Wheeler transform ⋮ String attractors and infinite words ⋮ A graph theoretic approach to automata minimality ⋮ Average case analysis of Moore's state minimization algorithm ⋮ Nondeterministic Moore automata and Brzozowski's minimization algorithm ⋮ A combinatorial view on string attractors ⋮ Standard Sturmian words and automata minimization algorithms ⋮ Hopcroft's algorithm and tree-like automata ⋮ Nondeterministic Moore Automata and Brzozowski’s Algorithm ⋮ A Challenging Family of Automata for Classical Minimization Algorithms

Uses Software

• AMoRE

Cites Work

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

This page was built for publication: On extremal cases of Hopcroft's algorithm