A1 Refereed original research article in a scientific journal

A note on short palindromes in square-free words




AuthorsTero Harju, Mike Müller

PublisherELSEVIER SCIENCE BV

Publication year2015

Journal:Theoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume562

First page 658

Last page659

Number of pages2

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2014.10.040


Abstract

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