A Note on Squares in Binary Words



: Harju Tero

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

: 2023

: International Journal of Foundations of Computer Science

: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

: INT J FOUND COMPUT S

: 6

: 0129-0541

: 1793-6373

DOI: https://doi.org/10.1142/S0129054123480052

: https://doi.org/10.1142/S0129054123480052

: https://arxiv.org/abs/2108.04572


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