Circular Sturmian words and Hopcroft's algorithm

DOI10.1016/j.tcs.2009.07.018zbMath1187.68360OpenAlexW2157313018MaRDI QIDQ732029

Antonio Restivo, Marinella Sciortino, Giuseppa Castiglione

Publication date: 9 October 2009

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

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

zbMATH Keywords

Sturmian morphismsdeterministic finite state automatacircular Sturmian wordsHopcroft's minimization algorithm

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

Novel results on the number of runs of the Burrows-Wheeler-transform, Tight lower and upper bounds for the complexity of canonical colour refinement, String attractors and infinite words, A graph theoretic approach to automata minimality, On extremal cases of Hopcroft's algorithm, A combinatorial view on string attractors, Standard Sturmian words and automata minimization algorithms, Distinct Squares in Circular Words, Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm, Characteristic Sturmian words are extremal for the critical factorization theorem, Nondeterministic Moore Automata and Brzozowski’s Algorithm, A Challenging Family of Automata for Classical Minimization Algorithms, On Extremal Cases of Hopcroft’s Algorithm, Minimisation of automata

Uses Software

• OEIS
• AMoRE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimisation of acyclic deterministic automata in linear time
• Repetitions in Sturmian strings
• Re-describing an algorithm by Hopcroft
• Characterisations of balanced words via orderings
• On an involution of Christoffel words and Sturmian morphisms
• Describing an algorithm by Hopcroft
• On Christoffel classes
• Hopcroft’s Algorithm and Cyclic Automata
• Implementation and Application of Automata