A Note on Squares in Binary Words

DOI10.1142/S0129054123480052arXiv2108.04572OpenAlexW3190619779MaRDI QIDQ6154976FDOQ6154976

Authors: Tero Harju 

Publication date: 16 February 2024

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

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$.

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)

Cites Work

• Title not available (Why is that?)
• A characterization of overlap-free morphisms
• The Morse sequence and iterated morphisms
• On the number of frames in binary words

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)