2014/05/22 by Chen Fei Du, Jeffrey Shallit
Computer Science · #cs.FL #cs.DM
paper · pdf · doi:10.4204/eptcs.151.16
published as EPTCS 151, 2014, pp. 231-245 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
We consider a measure of similarity for infinite words that generalizes the notion of asymptotic or natural density of subsets of natural numbers from number theory. We show that every overlap-free infinite binary word, other than the Thue-Morse word t and its complement t bar, has this measure of similarity with t between 1/4 and 3/4. This is a partial generalization of a classical 1927 result of Mahler.