Circular Sturmian words and Hopcroft's algorithm

DOI10.1016/J.TCS.2009.07.018MaRDI QIDQ732029zbMATH OpenOpenAlexFDO

Authors Antonio Restivo, G. Castiglione, M. Sciortino

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

circular Sturmian wordsdeterministic finite state automataHopcroft's minimization algorithmSturmian morphisms

Mathematics Subject Classification ID

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

Recommendations

• Hopcroft's automaton minimization algorithm and Sturmian words
• Hopcroft’s Algorithm and Cyclic Automata
• Standard Sturmian words and automata minimization algorithms
• Implementation and Application of Automata
• Hopcroft's algorithm and tree-like automata

Cites work

• Characterisations of balanced words via orderings
• Describing an algorithm by Hopcroft
• Hopcroft's automaton minimization algorithm and Sturmian words
• Hopcroft’s Algorithm and Cyclic Automata
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Implementation and Application of Automata
• Minimisation of acyclic deterministic automata in linear time
• On an involution of Christoffel words and Sturmian morphisms
• On Christoffel classes
• Re-describing an algorithm by Hopcroft
• Repetitions in Sturmian strings
• The On-Line Encyclopedia of Integer Sequences

Cited in

(17)

• On extremal cases of Hopcroft's algorithm
• Minimisation of automata
• A combinatorial view on string attractors
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Tight lower and upper bounds for the complexity of canonical colour refinement
• A challenging family of automata for classical minimization algorithms
• Hopcroft’s Algorithm and Cyclic Automata
• On Extremal Cases of Hopcroft’s Algorithm
• A graph theoretic approach to automata minimality
• Standard Sturmian words and automata minimization algorithms
• Distinct squares in circular words
• Nondeterministic Moore automata and Brzozowski's algorithm
• String attractors and infinite words
• New string attractor-based complexities for infinite words
• Bit catastrophes for the Burrows-Wheeler transform
• Characteristic Sturmian words are extremal for the critical factorization theorem
• Novel results on the number of runs of the Burrows-Wheeler-transform

Describes a project that uses

Uses Software

• AMoRE
• OEIS

This page was built for publication: Circular Sturmian words and Hopcroft's algorithm

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