On generating binary words palindromically

From MaRDI portal

Jump to:navigation, search

DOI10.1016/J.JCTA.2014.10.003MaRDI QIDQ472173zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

Sturmian word palindrome balanced word weakly rich word

Mathematics Subject Classification ID

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

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.

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)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=On_generating_binary_words_palindromically&oldid=77986601"