Name
Abstract | ||
|---|---|---|
Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if, it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. Also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.09.056 | Theoretical Computer Science |
Keywords | DocType | Volume |
Episturmian word,directive word,Sturmian case,Lexicographic order,Arnoux–Rauzy sequence,quasiperiodic Sturmian word,Sturmian word,infinite lyndon word,particular normalized directive word,Episturmian morphism,Infinite Lyndon word,episturmian word,infinite Lyndon word,Lyndon word,Quasiperiodicity,Lyndon episturmian word,quasiperiodicity.,episturmian mor- phism,lexicographic order,arnoux-rauzy sequence,sturmian word,return word,quasiperiodic episturmian word | Journal | 409 |
Issue | ISSN | Citations |
3 | Theoretical Computer Science | 9 |
PageRank | References | Authors |
0.64 | 28 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amy Glen | 1 | 121 | 9.48 |
| Florence Levé | 2 | 51 | 10.20 |
| Gwénaël Richomme | 3 | 136 | 18.10 |