On generating binary words palindromically

DOI10.1016/J.JCTA.2014.10.003zbMATH Open1307.68060OpenAlexW2133240281MaRDI QIDQ472173FDOQ472173

Authors: Mari Huova, Luca Q. Zamboni, Tero Harju

Publication date: 19 November 2014

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We regard a finite word

u = u_{1} u_{2} c d o t s u_{n}

up to word isomorphism as an equivalence relation on

1, 2, l d o t s, n

where

i

is equivalent to

j

if and only if

x_{i} = x_{j} .

Some finite words (in particular all binary words) are generated by "{it palindromic}" relations of the form

k s i m j + i - k

for some choice of

1 l e q i l e q j l e q n

and

k i n i, i + 1, l d o t s, 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

m u (u)

defined as the least number of palindromic relations required to generate

u .

We show that every aperiodic infinite word must contain a factor

u

with

m u (u) g e q 3,

and that some infinite words

x

have the property that

m u (u) l e q 3

for each factor

u

of

x .

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.

Full work available at URL: https://arxiv.org/abs/1309.1886

Recommendations

zbMATH Keywords

Sturmian word palindrome balanced word weakly rich word

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

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)