Enumeration of factors in the Thue-Morse word
type: Item
instance of: scholarly article
title: Enumeration of factors in the Thue-Morse word
zbMATH Open document ID: 0683.20045
DOI: 10.1016/0166-218X(92)90274-E
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: The infinite word of Thue-Morse M is the limit \(\lim_{n\to \infty}\phi^ n(a)\), where \(\phi\) is the endomorphism of the free monoid \(\{a,b\}^*\) defined by \(\phi (a)=ab\), \(\phi (b)=ba\). The author proves that if M is written \(w_ 1w_ 2\), then either \(w_ 1\) has a square suffix, or \(w_ 2\) has a square prefix. A byproduct of his methods allows him to deduce a result of Pansiot, which characterizes the square factors of M. Finally, he gives some results on the function \(P(m)=number\) of factors of length m of M, in particular \[ \liminf_{m\to \infty}P(m)/(m-1)=3\quad and\quad \limsup P(m)/(m- 1)=10/3. \]
reviewed by: Christophe Reutenauer
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4118609
zbMATH Keywords: Thue-Morse word
zbMATH Keywords: free monoid
zbMATH Keywords: square suffix
zbMATH Keywords: square prefix
zbMATH Keywords: square factors
zbMATH Keywords: number of factors
Wikidata QID: Q56288099
author: Srečko Brlek
MaRDI profile type: Publication
cites work: New estimates of odd exponents of infinite Burnside groups.
cites work: Magic Cubes and Prouhet Sequences
cites work: Q5767794
cites work: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
cites work: Q5735246
cites work: Q3659988
cites work: Unending chess, symbolic dynamics and a problem in semi-groups
cites work: INFINITE PERIODIC GROUPS. I
cites work: The Morse sequence and iterated morphisms
cites work: Rational languages and the Burnside problem
description: scientific article; zbMATH DE number 4118609