A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A Note on Squares in Binary Words
Tekijät: Harju Tero
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2023
Journal: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Lehden akronyymi: INT J FOUND COMPUT S
Sivujen määrä: 6
ISSN: 0129-0541
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S0129054123480052
Verkko-osoite: https://doi.org/10.1142/S0129054123480052
Preprintin osoite: https://arxiv.org/abs/2108.04572
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali