The subword complexity of finite and infinite binary words
Irina Gheorghiciuc · Scholarly Commons (University of Pennsylvania) · 2004
Let Aq be a q-letter alphabet and w be a finite or right infinite word on this alphabet. A subword of w is a block of consecutive letters of w. The subword complexity function of w assigns to each positive integer, n, the number, fw (n), of distinct subwords of length n of w. We will study general properties of the subword complexity function of infinite and finite words. We also give a method of computing the subword complexity of a class of infinite binary words. In Chapter 2 we discuss the background material in the combinatorics on words that motivates our work. Next, in Chapter 3, we introduce the key notion of the gap function of an infinite binary word and compute the subword complexity of a class of infinite binary words whose gap function satisfies certain conditions. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is strictly increasing is obtained. We also show that for any integers a > 1 and b there exists an infinite binary word in our class whose subword complexity function is ultimately an + b. Then, in Chapter 4, we prove a general result that connects the subword complexity of an infinite binary word with certain statistics on its prefixes. Finally, in Chapter 5, we use correlation polynomials and a famous result of Guibas and Odlyzko (Journal of Combinatorial Theory A30 (1981) pp. 183–208) to compute the expected number of distinct subwords of length k in a word of length n. We also prove a formula for the generating function that enumerates words of length n whose kth subword complexity is m.