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

JournalTheoretical 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