On highly palindromic words: the \(n\)-ary case
type: Item
instance of: scholarly article
title: On highly palindromic words: the \(n\)-ary case
zbMATH Open document ID: 1482.68189
author: Kristina Ago
author: Bojan Bašić
published in: Discrete Applied Mathematics
publication date: 2021-09-30T00:00:00Z
review text: A word of length \(m\) over an \(n\)-ary alphabet is called minimal-palindromic if its longest palindromic subword (or scattered factor) has length at most \(\lceil m/n \rceil\). The word \(rws\) over the same alphabet as \(w\) is an MP-extension of \(w\) if \(rws\) is minimal-palindromic. Extending results of [\textit{Š. Holub} and \textit{K. Saari}, Discrete Appl. Math. 157, No. 5, 953--959 (2009; Zbl 1187.68363); \textit{K. Ago} and \textit{B. Bašić}, Discrete Appl. Math. 284, 434--443 (2020; Zbl 1448.68363)], the authors show that any word \(w\) over an \(n\)-ary alphabet, \(n \geq 4\), has an MP-extension of length \(n M_n |w|\), and \(M_n\) is defined as \(M_4 = 4\), \(M_5 = 8\), and \(M_n = 2^{\lceil n/2 \rceil} + 2^{\lceil n/2 \rceil - 1} - 3\) for \(n\geq 6\). As a consequence, for any \(n\), the MP-ratio \(|rws|/|w|\), where \(rws\) is the shortest MP-extension of \(w\), of an \(n\)-ary word \(w\) is well-defined (and finite). Tight upper bounds for the MP-ratio of \(n\)-ary words are known for the cases \(n=2\) and \(n=3\) from the aforementioned references. The authors give a lower bound of \(2n\) on the maximal MP-ratio of \(n\)-ary words. To conclude, the authors show that minimal-palindromic words are abelian unbordered, that is, for every factorisation \(w = xuy\) of a minimal-palindromic word, the word \(x\) cannot be rearranged to obtain \(y\).
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 7404861
zbMATH Keywords: subword
zbMATH Keywords: palindrome
zbMATH Keywords: MP-ratio
zbMATH Keywords: abelian border
reviewed by: Markus A. Whiteland
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2021.07.020
OpenAlex ID: W4200234882
cites work: On highly palindromic words: the ternary case
cites work: Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
cites work: Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words
cites work: Dyck words, lattice paths, and abelian borders
cites work: Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
cites work: Palindromic length in linear time
cites work: ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
cites work: Abelian bordered factors and periodicity
cites work: Abelian borders in binary words
cites work: Identifying all abelian periods of a string in quadratic time and relevant problems
cites work: Q3396591
cites work: A note on efficient computation of all abelian periods in a string
cites work: Strongly non-repetitive sequences and progression-free sets
cites work: Episturmian words and some constructions of de Luca and Rauzy
cites work: Q3281093
cites work: Q5579506
cites work: Algorithms for computing abelian periods of words
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: On highly palindromic words
cites work: Abelian squares are avoidable on 4 letters
cites work: Fast algorithms for abelian periods in words and greatest common divisor queries
cites work: Q5646912
cites work: Palindromic length in free monoids and free groups
DOI: 10.1016/J.DAM.2021.07.020
Recommended article: On highly palindromic words: the ternary case
Recommended article: On highly palindromic words
Recommended article: Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words
Recommended article: On the least number of palindromes contained in an infinite word
Recommended article: A unique extension of rich words
Recommended article: On the least number of palindromes in two-dimensional words
Recommended article: Palindromic length of words with many periodic palindromes
Recommended article: On palindromic length of Sturmian sequences
Recommended article: A baba galamaga.
Recommended article: Smallest and Largest Block Palindrome Factorizations
description: scientific article; zbMATH DE number 7404861