Enumeration of irreducible binary words (Q1121031)

Denote by \(\Sigma^*\) the set of (finite, binary) words over an alphabet \(\Sigma =\{a,b\}\). For a language L over \(\Sigma\) the density \(d_ L(n)\) is defined as the number of words in L of length n. Let \(\Sigma^{\omega}\) be the set of infinite words over \(\Sigma\), i.e. of infinite (binary) sequences \(a_ 1a_ 2...a_ n..\). with all \(a_ i\in \Sigma\). A word \(x\in \Sigma^*\cup \Sigma^{\omega}\) is called irreducible if it is overlap free, i.e. it has no subword of the form yyc, where y is a nonempty word in \(\Sigma^*\) with the letter c, \(c\in \Sigma\), in the first position. A word is said to be irreducibly extensible if it is a left factor of some infinite irreducible word. Denote B the language of all irreducible words over \(\Sigma\) and let \(\bar B\) be the language of all irreducibly extensible words (over \(\Sigma)\). Accomplishing some investigations of \textit{A. Restivo} and \textit{S. Salemi} [Combinatorial Algorithms on Words, NATO ASI Ser., Ser. F 12, 289-295 (1985; Zbl 0604.68100)] the author shows here that the irreducible binary words grow slowly - he proves (Th. 16) that there is a constant C such that \(d_ B(n)<Cn^{1.587}\) for all \(n>0\). He proves also (Th. 8) that there exist positive constants \(C_ 1\) and \(C_ 2\) such that \(C_ 1n^{\theta}<d_{\bar B}(n)<C_ 2n^{\theta}\) for all \(n>0\) with \(\theta =\log_ 2\xi =1.155...\), where \(\xi =2.226..\). is the positive root of \(x^ 4-2x^ 3-x^ 2+2x-2\).