On highly palindromic words: the ternary case
type: Item
instance of: scholarly article
title: On highly palindromic words: the ternary case
zbMATH Open document ID: 1448.68363
author: Kristina Ago
author: Bojan Bašić
published in: Discrete Applied Mathematics
publication date: 2020-07-07T00:00:00Z
review text: The paper considers palindromes which are scattered subwords of a given finite word. A finite word \(w\) over an \(n\)-letter alphabet is called minimal-palindromic if the longest palindrome in it is of length \(\lceil |w|/n \rceil\); clearly, a palindrome of this length always exists as a subword of the prevalent letter. In [Discrete Appl. Math. 157, No. 5, 953--959 (2009; Zbl 1187.68363)], \textit{Š. Holub} and \textit{K. Saari} proved that each binary word can be extended to the left and to the right to a minimal palindromic word, and introduced the MP-ratio of a word \(w\) as the minimal ratio \(|pws|/|w|\), where \(pws\) is such an extension of \(w\). They also proved that for every binary word, the MP-ratio exists and is bounded from above by \(4\). In this paper, the analogous results are obtained for all ternary words: it is proven that the MP-ratio of a ternary word exists, is bounded from above by \(6\), and the bound is the best possible. The results are rather technical and the presentation is dense and complicated.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 7218289
zbMATH Keywords: scattered subword
zbMATH Keywords: palindrome
zbMATH Keywords: MP-ratio
zbMATH Keywords: word extension
reviewed by: Anna Frid
MaRDI profile type: Publication
full work available at URL: j.dam.2020.04.006
OpenAlex ID: W3016799184
cites work: Palindromic decompositions with gaps and errors
cites work: Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
cites work: Diverse Palindromic Factorization is NP-Complete
cites work: Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words
cites work: On highly potential words
cites work: Q5016359
cites work: Palindromic length in linear time
cites work: Greedy Palindromic Lengths
cites work: Abelian bordered factors and periodicity
cites work: Abelian borders in binary words
cites work: Episturmian words and some constructions of de Luca and Rauzy
cites work: Sturmian numeration systems and decompositions to palindromes
cites work: On palindromic factorization of words
cites work: Palindromic richness
cites work: ON THE NUMBER OF ABELIAN BORDERED WORDS (WITH AN EXAMPLE OF AUTOMATIC THEOREM-PROVING)
cites work: Palindromic rich words and run-length encodings
cites work: On highly palindromic words
cites work: Languages invariant under more symmetries: overlapping factors versus palindromic richness
cites work: On the number of rich words
cites work: Palindromic length in free monoids and free groups
cites work: Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
cites work: Rich square-free words
DOI: 10.1016/J.DAM.2020.04.006
description: scientific article; zbMATH DE number 7218289