On prefixal factorizations of words

DOI10.1016/J.EJC.2015.08.007zbMATH Open1333.68223arXiv1505.02309OpenAlexW2159630352WikidataQ114184794 ScholiaQ114184794MaRDI QIDQ896064FDOQ896064

Authors: Luca Q. Zamboni, Aldo De Luca

Publication date: 11 December 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider the class

{c a l P}_{1}

of all infinite words

x i n A^{o} m e g a

over a finite alphabet

A

admitting a prefixal factorization, i.e., a factorization

x = U_{0} U_{1} U_{2} c d o t s

where each

U_{i}

is a non-empty prefix of

x .

With each

x i n {c a l P}_{1}

one naturally associates a "derived" infinite word

d e l t a (x)

which may or may not admit a prefixal factorization. We are interested in the class

{c a l P}_{i n f t y}

of all words

x

of

{c a l P}_{1}

such that

d e l t a^{n} (x) i n {c a l P}_{1}

for all

n g e q 1

. Our primary motivation for studying the class

{c a l P}_{i n f t y}

stems from its connection to a coloring problem on infinite words independently posed by T. Brown in cite{BTC} and by the second author in cite{LQZ}. More precisely, let

be the class of all words

x i n A^{o} m e g a

such that for every finite coloring

v a r p h i : A^{+} i g h t a r r o w C

there exist

c i n C

and a factorization

x = V_{0} V_{1} V_{2} c d o t s

with

v a r p h i (V_{i}) = c

for each

i g e q 0.

In cite{DPZ} we conjectured that a word

if and only if

x

is purely periodic. In this paper we show that

so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of

{c a l P}_{i n f t y} .

We establish several results on the class

{c a l P}_{i n f t y}

. In particular, we show that a Sturmian word

x

belongs to

{c a l P}_{i n f t y}

if and only if

x

is nonsingular, i.e., no proper suffix of

x

is a standard Sturmian word.

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

Recommendations

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

Cited In (9)

This page was built for publication: On prefixal factorizations of words

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