Palindromic Length and Reduction of Powers

Abstract

Given a nonempty finite word $v$, let $PL(v)$ be the palindromic length of $v$; it means the minimal number of palindromes whose concatenation is equal to $v$. Let $v^R$ denote the reversal of $v$. Given a finite or infinite word $y$, let $Fac(y)$ denote the set of all finite factors of $y$ and let $maxPL(y)=\max \{PL(t)\mid t\in Fac(y)\}$. Let $x$ be an infinite non-ultimately periodic word with $maxPL(x)=k<\infty$ and let $u\in Fac(x)$ be a primitive nonempty factor such that $u^5$ is recurrent in $x$. Let $Ψ(x,u)=\{t\in Fac(x)\mid u,u^R\not\in Fac(t)\}\mbox{.}$ We construct an infinite non-ultimately periodic word $\overline{x}$ such that $u^5,(u^R{)}^5\notin Fac(\overline{x})$, $\Psi (x,u)\subseteq Fac(\overline{x})$, and $maxPL(\overline{x})\le 3k^3$. Less formally said, we show how to reduce the powers of $u$ and $u^R$ in $x$ in such a way that the palindromic length remains bounded.

Cited by in corpus (1)

• Palindromic length of infinite aperiodic words