Catalog Home Page

Order and quasiperiodicity in episturmian words

Glen, A. (2007) Order and quasiperiodicity in episturmian words. In: Sixth International Conference on Words, 17 - 21 September, Marseille, France

PDF (Extended Abstract) - Authors' Version
Download (219kB)
    PDF (Presentation) - Other
    Download (758kB) | Preview


      We prove a refinement of a recent characterization of infinite episturmian words via lexicographic orderings (Glen-Justin-Pirillo, 2007). This allows us to easily characterize the strict episturmian words that are "infinite Lyndon words", i.e., those that are lexicographically smaller than all of their proper suffixes. Another simple consequence is that a real number $\beta > 1$ is a so-called "self-episturmian number" if and only if the greedy $\beta$-expansion of 1 takes the form bS, where $b = \lfloor\beta\rfloor$ and S is a "strict epistandard sequence" on the alphabet {0,1,...,b}. F. Leve and G. Richomme recently characterized the non-quasiperiodic Sturmian words, proving that a Sturmian word is not quasiperiodic if and only if it is an infinite Lyndon word. With the aim of determining all of the non-quasiperiodic episturmian words, we first prove that an episturmian word is not quasiperiodic if it is directed by a "regular wavy word". This shows that there is a much wider class of episturmian words that are not quasiperiodic, besides those that are infinite Lyndon words. These results and others lead to a characterization of the (non)-quasiperiodic episturmian words with respect to their directive words. Moreover, we show that all epistandard words are quasiperiodic and completely describe all of their quasiperiods.

      Publication Type: Conference Paper
      Conference Website:
      Item Control Page


      Downloads per month over past year