On generating binary words palindromically

We 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

m u

is unbounded.

Review text

The paper deals with a description of words based on their palindromic factors. Let \(u[ i,j] \) denote the factor \(u_{i}\cdots u_{j}\) of a word \(u=u_{1}u_{2}\cdots u_{n}\). A word \(u\in\mathbb{A}^{n}\) is palindromically generated by a set of pairs \(S=\{ (i,j)\mid 1\leq i\leq j\leq n\} \) such that if 1. \(u[i,j] _{j}\) is a palindrome for each \((i,j) \in S\) and 2. if \(v\in\mathbb{B}^{n}\) is a word such that \(v[ i,j] \) is a palindrome for each \((i,j) \in S\), then there exists an alphabetic (induced by a mapping \(c:\mathbb{A\to B}\)) morphism \(c:\mathbb{A}^{\ast}\to \mathbb{B}^{\ast}\) such that \(c(u) =v\). Every word over a binary alphabet can be palindromically generated; this is not the case for larger alphabets. The parameter \(\mu(u) \) is defined for a word \(u\) as the size of the smallest set \(S\) palindromically generating \(u\). For an infinite word \(x\), let \(\psi(x) =\sup\{ \mu(u)\mid u\text{ is a factor of }x\} \). The main results may be summarized as follows: A binary word \(u\) is a factor of a double Sturmian word iff \(\mu(u) \leq3\) (a word is double Sturmian if it is a suffix of an image of some Sturmian word in a morphism, which doubles occurrences of some symbol(s) of the binary alphabet \(\{0,1\} \) and keeps the occurrences of the remaining one(s) single). An infinite\ binary word \(x\) is double Sturmian iff \(\psi(x) =3\). A palindromically generated word is weakly rich (a word is weakly rich if for every symbol \(a\) all complete returns of \(a\) are palindromes; a complete return of a word \(u\) in a word \(w\) is a factor \(r\neq u\) of \(w\) such that \(u\) occurs in \(r\) precisely twice, once as its prefix and once as its suffix -- unfortunately, these definitions are not included in the paper). If an infinite word \(x\) is aperiodic then \(\psi(x) \geq3\). For \(t\) the infinite word of Thue-Morse, \(\psi(t) =\infty\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On generating binary words palindromically

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472173)