On longest palindromic subwords of finite binary words

DOI10.1016/J.DISC.2021.112493MaRDI QIDQ2037574zbMATH OpenOpenAlexFDO

Authors Jan Petr, Jan Soukup

Publication date 8 July 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2021.112493

zbMATH Keywords

binary wordscircular wordspalindromespalindromic subwords

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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\).

Recommendations

• Palindromic subsequences in finite words
• Palindromes in circular words
• Greedy palindromic lengths
• On highly palindromic words
• Palindromic length of words with many periodic palindromes

Cites work

• Palindromic subsequences in finite words

Cited in

(4)

• On a theorem concerning partially overlapping subpalindromes of a binary word
• Palindromic subsequences in finite words
• Palindromes in circular words
• On binary palindromes of the form \(10^n\pm 1\)

This page was built for publication: On longest palindromic subwords of finite binary words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037574)