[Back]

C. Müllner, A. Ryzhikov:
"Palindromic subsequences in finite words";
Lecture Notes in Computer Science, 11417 (2019).

In 1999 Lyngsø and Pedersen proposed a conjecture stating that every binary circular word of length n with equal number of zeros and ones has an antipalindromic linear subsequence of length at least 23n. No progress over a trivial 12n bound has been achieved since then. We suggest a palindromic counterpart to this conjecture and provide a non-trivial infinite series of circular words which prove the upper bound of 23n for both conjectures at the same time. The construction also works for words over an alphabet of size k and gives rise to a generalization of the conjecture by Lyngsø and Pedersen. Moreover, we discuss some possible strengthenings and weakenings of the named conjectures. We also propose two similar conjectures for linear words and provide some evidences for them.

http://dx.doi.org/10.1007/978-3-030-13435-8_34