Complexity of Substitutive Sequences - Calculation of the Complexities of Substitutive Sequences Over a Binary Alphabet
arXiv:1507.03058
Abstract
We consider the complexities of substitutive sequences over a binary alphabet. By studying various types of special words, we show that, knowing some initial values, its complexity can be completely formulated via a recurrence formula determined by the characteristic polynomial.
16 pages