La complejidad de Thue-Morse Secuencia

Question

Considerar el alfabeto $\mathcal{A}=\{0,1\}$ y la sustitución de la $\phi$ dada por $ \phi(0)=01$, $\phi(1)=10$. Deje $t$ ser el punto dado por $t=\lim_{n\rightarrow\infty}\phi^n(0)$. A continuación, $t$ es el Thue-Morse secuencia; su primer par de caracteres $0110100110010\ldots$.

Podemos definir la complejidad de una palabra $u$ como un mapa de $F_u:\mathbb{N}\rightarrow\mathbb{N}$, de tal manera que para todos los $n\in\mathbb{N}$, $F_u(n)$ es igual al número de los distintos subpalabras de $u$ de la longitud de la $n$.

Alguien ha calculado la complejidad de la función de la Thue-Morse secuencia? He intentado encontrar algunas fuentes, pero no han tenido éxito. Todas las referencias son la mayoría de la recepción.

Answer 1

De acuerdo a la Wikipedia en francés página en la Prouhet-Thue-Morse secuencia, la complejidad de la función $c(n)$ de la Thue-Morse es la secuencia de la secuencia de A005942 en OEIS. Se puede calcular de la siguiente manera. Para $n \geqslant 1$, vamos a $k \geqslant 0$ ser el número entero tal que $2^k + 1 \leqslant n \leqslant 2^{k + 1}$ and let $r$ be such that $n = 2^k + r$, con $1\leqslant r\leqslant 2^{k}$. Entonces $$ c(n)= \begin{cases} 3\cdot 2^{k}+4(r-1)&{\text{if }}1 \leqslant r \leqslant 2^{k-1},\\ 4\cdot 2^{k}+2(r-1)&{\text{if }}2^{k-1}+1\leqslant r \leqslant 2^{k}. \end{casos} $$ Por otra parte, $c(n) \leqslant \frac{10}{3}n$ todos los $n$. Las referencias pertinentes (de la OEIS):

[1] J.-P. Allouche y J. Shallit, Secuencias Automáticas, Cambridge Univ. Press, 2003. Véase el Problema 10, pág. 335.

[2] J. Berstel et al., La combinatoria de Palabras: Christoffel Palabras y Repeticiones de Palabras, Amer. De matemáticas. Soc., 2008. Ver p. 83.

[3] S. Brlek, la Enumeración de los factores en el Thue-Morse palabra, Discretas Matemáticas Aplicadas. 24 (1989), 83-96.

[4] A. De Luca, S. Varricchio, Algunas propiedades combinatorias de la Thue-Morse secuencia y un problema en semigroups. Theoret. Comput. Sci. 63 (1989), no. 3, 333-348.