Block Growth

Let $(x_0 x_1 x_2 \ldots)$ be a sequence over a finite Alphabet $A$ (all the entries are elements of $A$). Define the block growth function $B(n)$ of a sequence to be the number of Admissible words of length $n$. For example, in the sequence $aabaabaabaabaab$..., the following words are Admissible

Length	Admissible Words
1	$a,b$
2	$aa, ab, ba$
3	$aab, aba, baa$
4	$aaba, abaa, baab$

so $B(1)=2$, $B(2)=3$, $B(3)=3$, $B(4)=3$, and so on. Notice that $B(n) \leq B(n+1)$, so the block growth function is always nondecreasing. This is because any Admissible word of length $n$ can be extended rightwards to produce an Admissible word of length $n+1$. Moreover, suppose $B(n) = B(n+1)$ for some $n$. Then each admissible word of length $n$ extends to a unique Admissible word of length $n+1$.

For a Sequence in which each substring of length $n$ uniquely determines the next symbol in the Sequence, there are only finitely many strings of length $n$, so the process must eventually cycle and the Sequence must be eventually periodic. This gives us the following theorems:

1. If the Sequence is eventually periodic, with least period $p$, then $B(n)$ is strictly increasing until it reaches $p$, and $B(n)$ is constant thereafter.

2. If the Sequence is not eventually periodic, then $B(n)$ is strictly increasing and so $B(n) \geq n+1$ for all $n$. If a Sequence has the property that $B(n) = n+1$ for all $n$, then it is said to have minimal block growth, and the Sequence is called a Sturmian Sequence.

The block growth is also called the Growth Function or the Complexity of a Sequence.