On prefixal factorizations of words

详细信息    查看全文

• 作者：Aldo de Luca^a ; ^{aldo.deluca@unina.it" class="auth_mail" title="E-mail the corresponding author} ; Luca Q. Zamboni^c ; ^b ; ^{lupastis@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：52
• 期：part_PA
• 页码：59-73
• 全文大小：429 K

文摘

We consider the class P₁${\mathcal{P}}_1$ of all infinite words x∈A^ω$x\in {\mathbb{A}}^{\omega }$ over a finite alphabet A$\mathbb{A}$ admitting a prefixal factorization, i.e., a factorization x=U₀U₁U₂⋯$x=U_0{U}_1{U}_2\cdots$ where each U_i$U_i$ is a non-empty prefix of x$x$. With each x∈P₁$x\in {\mathcal{P}}_1$ one naturally associates a “derived” infinite word δ(x)$\delta \left(x\right)$ which may or may not admit a prefixal factorization. We are interested in the class P_∞${\mathcal{P}}_{\infty }$ of all words x$x$ of P₁${\mathcal{P}}_1$ such that δⁿ(x)∈P₁${\delta }^n\left(x\right)\in {\mathcal{P}}_1$ for all n≥1$n\ge 1$. Our primary motivation for studying the class P_∞${\mathcal{P}}_{\infty }$ 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\in {\mathbb{A}}^{\omega }$ such that for every finite coloring φ:A⁺→C$\phi :{\mathbb{A}}^{+}\to C$ there exist c∈C$c\in C$ and a factorization x=V₀V₁V₂⋯$x=V_0{V}_1{V}_2\cdots$ with φ(V_i)=c$\phi \left(V_i\right)=c$ for each i≥0$i\ge 0$. In a recent paper (de Luca et al., 2014), we conjectured that a word $x\in P$ if and only if x$x$ is purely periodic. In this paper we prove that $P⊊{\mathcal{P}}_{\infty }$, so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of P_∞${\mathcal{P}}_{\infty }$. We establish several results on the class P_∞${\mathcal{P}}_{\infty }$. In particular, we prove that a Sturmian word x$x$ belongs to P_∞${\mathcal{P}}_{\infty }$ if and only if x$x$ is nonsingular, i.e., no proper suffix of x$x$ is a standard Sturmian word.