A1 Refereed original research article in a scientific journal

A Note on Squares in Binary Words




AuthorsHarju Tero

PublisherWORLD SCIENTIFIC PUBL CO PTE LTD

Publication year2023

JournalInternational Journal of Foundations of Computer Science

Journal name in sourceINTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Journal acronymINT J FOUND COMPUT S

Number of pages6

ISSN0129-0541

eISSN1793-6373

DOIhttps://doi.org/10.1142/S0129054123480052(external)

Web address https://doi.org/10.1142/S0129054123480052(external)

Preprint addresshttps://arxiv.org/abs/2108.04572(external)


Abstract
We consider words over a binary alphabet. A word w is overlap-free if it does not have factors (blocks of consecutive letters) of the form uvuvu for nonempty u. Let M(w) denote the number of positions that are middle positions of squares (of the form uu) in w. We show that for overlap-free binary words, 2M(w) = |w| + 3, and that there are infinitely many overlap-free binary words for which 2M(w) = |w| + 3.



Last updated on 2024-26-11 at 20:19