×

Enumeration of irreducible binary words. (English) Zbl 0673.68046

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

MSC:

68Q45 Formal languages and automata
05A15 Exact enumeration problems, generating functions
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0604.68100
PDFBibTeX XMLCite
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.