Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653344 | European Journal of Combinatorics | 2016 | 15 Pages |
We consider the class P1P1 of all infinite words x∈Aωx∈Aω over a finite alphabet AA admitting a prefixal factorization, i.e., a factorization x=U0U1U2⋯x=U0U1U2⋯ where each UiUi is a non-empty prefix of xx. With each x∈P1x∈P1 one naturally associates a “derived” infinite word δ(x)δ(x) which may or may not admit a prefixal factorization. We are interested in the class P∞P∞ of all words xx of P1P1 such that δn(x)∈P1δn(x)∈P1 for all n≥1n≥1. Our primary motivation for studying the class P∞P∞ stems from its connection to a coloring problem on infinite words independently posed by T. Brown and by the second author. More precisely, let P be the class of all words x∈Aωx∈Aω such that for every finite coloring φ:A+→Cφ:A+→C there exist c∈Cc∈C and a factorization x=V0V1V2⋯x=V0V1V2⋯ with φ(Vi)=cφ(Vi)=c for each i≥0i≥0. In a recent paper (de Luca et al., 2014), we conjectured that a word x∈P if and only if xx is purely periodic. In this paper we prove that P⊊P∞, so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of P∞P∞. We establish several results on the class P∞P∞. In particular, we prove that a Sturmian word xx belongs to P∞P∞ if and only if xx is nonsingular, i.e., no proper suffix of xx is a standard Sturmian word.