• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Minimal Factorizations of Words as Products of Palindromes

Anna Frid, Svetlana Puzynina, Luca Q. Zamboni, On Minimal Factorizations of Words as Products of Palindromes. TUCS Technical Reports 1063, TUCS, 2012.

Abstract:

Given a finite word $u$, we define its palindromic length $|u|_{\rm pal}$ to be the least number $n$ such that $u=v_1v_2\dots v_n$ with each $v_i$ a palindrome. We address the following open question: Does there exist an infinite non ultimately periodic word $w$ and a positive integer $P$ such that $|u|_{\rm pal} \leq P$ for each factor $u$ of $w$? We give a partial answer to this question by proving that if an infinite word $w$ satisfies the so-called $(k,l)$-condition for some $k$ and $l$, then for each positive integer $P$ there exists a factor $u$ of $w$ whose palindromic length $|u|_{\rm pal}>P$. In particular, the result holds for all the $k$-power-free words and for the Sierpinski word.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tFrPuZa12a,
  title = {On Minimal Factorizations of Words as Products of Palindromes},
  author = {Frid, Anna and Puzynina, Svetlana and Zamboni, Luca Q.},
  number = {1063},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2012},
  keywords = {palindrome, periodicity of words, complexity of words},
  ISBN = {978-952-12-2829-2},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication