×

On longest palindromic subwords of finite binary words. (English) Zbl 1482.68190

The authors disprove a conjecture on palindromic (scattered) subwords of circular words, stated by C. Müllner and 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\).

MSC:

68R15 Combinatorics on words

Citations:

Zbl 1425.68334
Full Text: DOI

References:

[1] Lyngsø, R.; Pedersen, C., Protein folding in the 2D HP model, BRICS Report Ser., 6, 16 (Jan. 1999)
[2] Müllner, C.; Ryzhikov, A., Palindromic subsequences in finite words, (Martín-Vide, C.; Okhotin, A.; Shapira, D., Language and Automata Theory and Applications (2019), Springer International Publishing: Springer International Publishing Cham), 460-468 · Zbl 1425.68334
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.