Palindromic length of words with many periodic palindromes

DOI10.1007/978-3-030-62536-8_14MaRDI QIDQ2040420zbMATH OpenOpenAlexFDO

Authors Josef Rukavicka

Publication date 14 July 2021

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

zbMATH Keywords

palindromepalindromic decompositionpalindromic length

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: The palindromic length $extPL(v)$ of a finite word $v$ is the minimal number of palindromes whose concatenation is equal to $v$. In 2013, Frid, Puzynina, and Zamboni conjectured that: If $w$ is an infinite word and $k$ is an integer such that $extPL(u)leqk$ for every factor $u$ of $w$ then $w$ is ultimately periodic. Suppose that $w$ is an infinite word and $k$ is an integer such $extPL(u)leqk$ for every factor $u$ of $w$. Let $Omega(w,k)$ be the set of all factors $u$ of $w$ that have more than $sqrt[k]k^{-1}vertuvert$ palindromic prefixes. We show that $Omega(w,k)$ is an infinite set and we show that for each positive integer $j$ there are palindromes $a,b$ and a word $uinOmega(w,k)$ such that $(ab{)}^j$ is a factor of $u$ and $b$ is nonempty. Note that $(ab{)}^j$ is a periodic word and $(ab{)}^{i}a$ is a palindrome for each $ileqj$. These results justify the following question: What is the palindromic length of a concatenation of a suffix of $b$ and a periodic word $(ab{)}^j$ with "many" periodic palindromes? It is known that $lvertextPL(uv)-extPL(u)vertleqextPL(v)$, where $u$ and $v$ are nonempty words. The main result of our article shows that if $a,b$ are palindromes, $b$ is nonempty, $u$ is a nonempty suffix of $b$, $vertabvert$ is the minimal period of $aba$, and $j$ is a positive integer with $jgeq3extPL(u)$ then $extPL(u(ab{)}^j)-extPL(u)geq0$.

Review text

Let \(\operatorname{PL}(u)\) denote the palindromic length of a finite word \(u\), that is, the minimal number of palindromes such that \(u\) is their concatenation. The main result of the article is the following: if \(a\), \(b\) are palindromes, \(b\) is nonempty, \(u\) is a nonempty suffix of \(b\), \(|ab|\) is the minimal period of \(aba\), and \(j\) is a positive integer with \(j\geq 3\operatorname{PL}(u)\), then \(\operatorname{PL}(u(ab) j )-\operatorname{PL}(u)\geq 0\). This result may be useful for a proof of the 2013 conjecture of [\textit{A. E. Frid} et al., Adv. Appl. Math. 50, No. 5, 737--748 (2013; Zbl 1285.68133)] that if the palindromic length of factors of an infinite word is bounded, then the word is ultimately periodic. Another result of the paper, Corollary 1, straighforwardly follows from results of [Zbl 1285.68133]. For the entire collection see [Zbl 1465.68022].

Recommendations

• On palindromic factorization of words
• Greedy palindromic lengths
• First lower bounds for palindromic length
• Palindromic length in free monoids and free groups
• On prefix palindromic length of automatic words

Cited in

(14)

• On highly palindromic words
• Palindromic length in free monoids and free groups
• On longest palindromic subwords of finite binary words
• Prefix palindromic length of the Sierpinski word
• Palindromic length and reduction of powers
• On highly palindromic words: the \(n\)-ary case
• On prefix palindromic length of automatic words
• First lower bounds for palindromic length
• Greedy palindromic lengths
• Prefix palindromic length of the Thue-Morse word
• The optimal upper bound on the MP-ratio for quaternary words
• And now there are four: another brick in the wall of the optimal upper bound on the MP-ratio
• Palindromic length of infinite aperiodic words
• Words with many palindrome pair factors

This page was built for publication: Palindromic length of words with many periodic palindromes

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