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.

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

      Abstract

      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: http://iml.univ-mrs.fr/words2007/accepted.en.html
      URI: http://researchrepository.murdoch.edu.au/id/eprint/3890
      Item Control Page

      Downloads

      Downloads per month over past year