A1 Refereed original research article in a scientific journal
A note on short palindromes in square-free words
Authors: Tero Harju, Mike Müller
Publisher: ELSEVIER SCIENCE BV
Publication year: 2015
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 562
First page : 658
Last page: 659
Number of pages: 2
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2014.10.040
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.