A note on short palindromes in square-free words




Tero Harju, Mike Müller

PublisherELSEVIER SCIENCE BV

2015

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

THEOR COMPUT SCI

562

658

659

2

0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2014.10.040(external)



A set A subset of N is called sparse if, for some No, the distance between any two elements of A is at least N-0. James Currie (2008) [2] showed that for each sparse set A and every subset P subset of A there exists a ternary square-free word w(P) such that a palindrome of length three starts at position i is an element of A in w(P) if and only if i is an element of P. We provide a simpler proof of this result that also works for shorter distances between the positions.




Last updated on 2024-26-11 at 17:41