Kobayashi, Yuji Enumeration of irreducible binary words. (English) Zbl 0673.68046 Discrete Appl. Math. 20, No. 3, 221-232 (1988). 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 A. Restivo and 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\). Reviewer: U.Kaljulaid Cited in 19 Documents MSC: 68Q45 Formal languages and automata 05A15 Exact enumeration problems, generating functions 68Q25 Analysis of algorithms and problem complexity Keywords:irreducible binary words; density of language Citations:Zbl 0604.68100 PDFBibTeX XMLCite \textit{Y. Kobayashi}, Discrete Appl. Math. 20, No. 3, 221--232 (1988; Zbl 0673.68046) Full Text: DOI References: [1] Brandenburg, F.-J., Uniformly growing \(k\)-th power-free homomorphisms, Theoret. Comput. Sci., 23, 69-82 (1983) · Zbl 0508.68051 [2] Fife, E. D., Binary sequences which contains no BBb, Trans. Amer. Math. Soc., 261, 115-136 (1980) · Zbl 0464.05018 [3] Kobayashi, Y., Repetition free words, Theoret. Comput. Sci., 44, 175-197 (1986) · Zbl 0596.20058 [4] Liu, C. L., Introduction to Combinatorial Mathematics (1968), McGraw-Hill: McGraw-Hill New York · Zbl 0188.03801 [5] Morse, M.; Hedlund, G. A., Unending chess, symbolic dynamics and a problem in semigroups, Duke Math J., 11, 1-7 (1944) · Zbl 0063.04115 [6] Restivo, A.; Salemi, S., Some decision results on nonrepetive words, (Combinatorial Algorithms on Words, Computer and System Science, 12 (1985), Springer: Springer Heidenberg), 289-295 [7] Thue, A., Ueber unendliche Zeichenreihe, Norske Vid. Selsk. Skr., 1, Math. Nat. Kl. Christiana, VII, 1-22 (1906) [8] Thue, A., Ueber die gegenseitige lage gleicher Teile gewisser Zeichenreihen, Math. Nat. Kl. Christiana, I, 1-67 (1912) · JFM 44.0462.01 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.