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\).
They also prove that the maximal length of \(qq^R\) cannot be less than \(3n/8\).
Reviewer: Anna Frid (Marseille)
MSC:
68R15 | Combinatorics on words |
Citations:
Zbl 1425.68334References:
[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.