A1 Refereed original research article in a scientific journal

On generating binary words palindromically




AuthorsTero Harju, Mari Huova, Luca Q. Zamboni

PublisherAcademic Press Inc.

Publication year2015

JournalJournal of Combinatorial Theory, Series A

Journal name in sourceJournal of Combinatorial Theory. Series A

Volume129

First page 142

Last page159

Number of pages18

ISSN0097-3165

DOIhttps://doi.org/10.1016/j.jcta.2014.10.003

Web address http://api.elsevier.com/content/abstract/scopus_id:84908254391


Abstract

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.




Last updated on 2024-26-11 at 22:32