A1 Refereed original research article in a scientific journal
A Note on Squares in Binary Words
Authors: Harju Tero
Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD
Publication year: 2023
Journal: International Journal of Foundations of Computer Science
Journal name in source: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Journal acronym: INT J FOUND COMPUT S
Number of pages: 6
ISSN: 0129-0541
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S0129054123480052(external)
Web address : https://doi.org/10.1142/S0129054123480052(external)
Preprint address: https://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.
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.
UTU Research Portal