Complexity of Substitutive Sequences - Calculation of the Complexities of Substitutive Sequences Over a Binary Alphabet

Bo Tan, Zhi-Xiong Wen, Yiping Zhang

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…