A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On generating binary words palindromically
Tekijät: Tero Harju, Mari Huova, Luca Q. Zamboni
Kustantaja: Academic Press Inc.
Julkaisuvuosi: 2015
Journal: Journal of Combinatorial Theory, Series A
Tietokannassa oleva lehden nimi: Journal of Combinatorial Theory. Series A
Vuosikerta: 129
Aloitussivu: 142
Lopetussivu: 159
Sivujen määrä: 18
ISSN: 0097-3165
DOI: https://doi.org/10.1016/j.jcta.2014.10.003
Verkko-osoite: http://api.elsevier.com/content/abstract/scopus_id:84908254391
We regard a finite word u=uu⋯u up to word isomorphism as an equivalence relation on {1, 2, . . ., n} where i is equivalent to j if and only if u=u. Some finite words (in particular all binary words) are generated by palindromic relations of the form k~j+i-k for some choice of 1≤i≤j≤n and k∈{i, i+1, . . ., j}. That is to say, some finite words u are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. In this paper we study the function μ(u) defined as the least number of palindromic relations required to generate u. We show that if x is an infinite word such that μ(u)≤2 for each factor u of x, then x is ultimately periodic. On the other hand, we establish the existence of non-ultimately periodic words for which μ(u)≤3 for each factor u of x, and obtain a complete classification of such words on a binary alphabet (which includes the well known class of Sturmian words). In contrast, for the Thue-Morse word, we show that the function μ is unbounded.