On longest palindromic subwords of finite binary words
type: Item
instance of: scholarly article
title: On longest palindromic subwords of finite binary words
zbMATH Open document ID: 1482.68190
author: Jan Petr
author: Jan Soukup
published in: Discrete Mathematics
publication date: 2021-07-08T00:00:00Z
review text: The authors disprove a conjecture on palindromic (scattered) subwords of circular words, stated by \textit{C. Müllner} and \textit{A. Ryzhikov} [Lect. Notes Comput. Sci. 11417, 460--468 (2019; Zbl 1425.68334)]. Namely, they find a series of circular words of the form \(w_1w_2w_3w_4\) of length \(n\) such that the longest palindrome \(p = qq^R\) of an even length such that either \(q\) is a subword of \(w_1 w_2\) and of \((w_3 w_4)^R\) or \(q\) is a subword of \(w_2 w_3\) and of \((w_4 w_1)^R\) is of length less than \(n/2\). The shortest of these examples is of length \(10000\), and the limit of the length of \(qq^R\) is \(15n/32\). They also prove that the maximal length of \(qq^R\) cannot be less than \(3n/8\).
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 7369632
zbMATH Keywords: palindromes
zbMATH Keywords: binary words
zbMATH Keywords: palindromic subwords
zbMATH Keywords: circular words
reviewed by: Anna Frid
MaRDI profile type: Publication
full work available at URL: j.disc.2021.112493
OpenAlex ID: W3168066995
cites work: Palindromic subsequences in finite words
DOI: 10.1016/J.DISC.2021.112493
description: scientific article; zbMATH DE number 7369632