A Note on Squares in Binary Words

DOI10.1142/S0129054123480052MaRDI QIDQ6154976zbMATH OpenOpenAlexFDO

Authors Tero Harju

Publication date 16 February 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.04572

zbMATH Keywords

squarebinary wordoverlap-free wordcentre of a square

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx) Semigroups (20Mxx)

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 in $w$. We show that for overlap-free binary words, $2M(w)le|w|+3$, and that there are infinitely many overlap-free binary words for which $2M(w)=|w|+3$.

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• A characterization of overlap-free morphisms
• On the number of frames in binary words
• The Morse sequence and iterated morphisms

This page was built for publication: A Note on Squares in Binary Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154976)