Circular Sturmian words and Hopcroft's algorithm
From MaRDI portal
Publication:732029
DOI10.1016/J.TCS.2009.07.018zbMATH Open1187.68360OpenAlexW2157313018MaRDI QIDQ732029FDOQ732029
M. Sciortino, Antonio Restivo, G. 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
Sturmian morphismsdeterministic finite state automatacircular Sturmian wordsHopcroft's minimization algorithm
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The On-Line Encyclopedia of Integer Sequences
- Characterisations of balanced words via orderings
- On an involution of Christoffel words and Sturmian morphisms
- Re-describing an algorithm by Hopcroft
- On Christoffel classes
- Implementation and Application of Automata
- Describing an algorithm by Hopcroft
- Minimisation of acyclic deterministic automata in linear time
- Hopcroft’s Algorithm and Cyclic Automata
- Repetitions in Sturmian strings
Cited In (17)
- Novel results on the number of runs of the Burrows-Wheeler-transform
- Tight lower and upper bounds for the complexity of canonical colour refinement
- A graph theoretic approach to automata minimality
- Minimal forbidden factors of circular words
- Minimisation of automata
- Hopcroft’s Algorithm and Cyclic Automata
- Nondeterministic Moore Automata and Brzozowski’s Algorithm
- New string attractor-based complexities for infinite words
- On extremal cases of Hopcroft's algorithm
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- Standard Sturmian words and automata minimization algorithms
- Characteristic Sturmian words are extremal for the critical factorization theorem
- On Extremal Cases of Hopcroft’s Algorithm
- A combinatorial view on string attractors
- Distinct Squares in Circular Words
- String attractors and infinite words
- A Challenging Family of Automata for Classical Minimization Algorithms
Uses Software
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)
