Let be a sequence over a finite Alphabet (all the entries are elements of ). Define the block growth function of a sequence to be the number of Admissible words of length . For example, in the sequence ..., the following words are Admissible

Length | Admissible Words |

1 | |

2 | |

3 | |

4 |

so , , , , and so on. Notice that
, so the block growth function is
always nondecreasing. This is because any Admissible word of length can be extended rightwards to produce an
Admissible word of length . Moreover, suppose for some . Then each admissible word of
length extends to a *unique* Admissible word of length .

For a Sequence in which each substring of length uniquely determines the next symbol in the Sequence, there are only finitely many strings of length , 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 , then is strictly increasing until it reaches , and is constant thereafter.
- 2. If the Sequence is not eventually periodic, then is strictly increasing and so for all . If a Sequence has the property that for all , 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.

© 1996-9

1999-05-26