Subpalabras de la palabra Fibonacci

Question

En Palabra Fibonacci es el límite de la secuencia de palabras que empiezan por " $0$ " y el cumplimiento de las normas $0 \to 01, 1 \to 0$ . Es equivalente a tener condiciones iniciales $S_0 = 0, S_1 = 01$ y luego la recursión $S_n= S_{n-1}S_{n-2}$ .

Quiero saber qué palabras no pueden aparecer como subpalabras en el límite $S_\infty$ . Al principio pensé $000$ y $11$ fueron los dos únicos que no pudieron aparecer. Entonces me di cuenta de que $010101$ . ¿Existe alguna caracterización de las palabras que pueden o no aparecer como subpalabras de la palabra Fibonacci?

Relacionada vagamente, esta palabra aparece como la secuencia de corte de la línea de pendiente $\phi^{-1}$ a través del origen donde $\phi = \frac{1 + \sqrt{5}}{2}$ .

Answer 1

La palabra Fibonacci es una de las Palabras esturiónicas por lo que su complejidad es $n+1$ es decir, el número de subpalabras diferentes de longitud $n$ es $n+1$ .para cada $n $ . Así que la mayoría de las palabras no son subpalabras de la palabra Fibonacci. Existen, que yo recuerde, 12 definiciones diferentes pero equivalentes de palabras esturmianas. Algunas de ellas imponen restricciones a las posibles subpalabras (véase Combinatoria algebraica de las palabras, de Lothaire, y un artículo de Berstel al respecto).

Answer 2

La forma más sencilla (en tiempo lineal, computacionalmente hablando) de determinar si una palabra finita $w$ es un factor (una subpalabra) de la palabra Fibonacci $S_\infty$ es la siguiente:

• Eliminar un 0 final de $w$ si está presente (sólo uno); si $w$ empieza por 1, añada un 0 inicial;
• La palabra así obtenida debe ser parseada unívocamente con (escrita como una concatenación de) 0 y 01; si no, entonces $w$ no es un factor de $S_\infty$ y ya está. Si $w=x_1x_2\cdots x_k$ es un análisis sintáctico de este tipo, dejemos que $y_i=0$ para todos $i$ tal que $x_i=01$ y $y_i=1$ en caso contrario (es decir, si $x_i=0$ ).
• Aplicar el mismo algoritmo a la nueva palabra $w'=y_1\cdots y_k$
• El original $w$ es un factor de $S_\infty$ si y sólo si se llega finalmente a la palabra 0 ó 1 aplicando recursivamente el procedimiento anterior.

La corrección puede demostrarse fácilmente, ya que la palabra Fibonacci es el límite de la sustitución $0\to 01$ , $1\to 0$ (folclore, véase, por ejemplo, Lothaire's Combinatoria algebraica de palabras ). Por ejemplo, $w=1010010010100$ es un factor ya que la secuencia de palabras generada por el algoritmo anterior es: $$w,\: 00101001,\: 10010,\: 010,\: 0\;.$$

Desde un punto de vista más dinámico, los desplazamientos de Sturm (como Fibonacci) no son ni de tipo finito ni sóficos. Sin embargo, no es difícil obtener la lista de factores mínimos prohibidos de la palabra Fibonacci, como sigue. Sea $S_i'$ sea el $i$ -enésimo prefijo palindrómico de $S_\infty$ que se obtiene eliminando los dos últimos caracteres de $S_i$ . Entonces una palabra finita $w$ es un factor de la palabra Fibonacci si y sólo si no contiene ninguno de los siguientes como factores, para todo $k\geq 1$ : $$1S_{2k-1}'1,\quad 0S_{2k}'0\;.$$ En otros términos, la secuencia de factores mínimos prohibidos es 11, 000, 10101, 00100100, 1010010100101, Véase, por ejemplo, Mignosi et al., Palabras y factores prohibidos

Answer 3

La sucesión de Fibonacci es una sucesión cuasiperiódica. Las secuencias cuasiperiódicas (y, de forma más general, los entramados cuasiperiódicos) pueden generarse, por ejemplo, mediante el "método de proyección de bandas". A grandes rasgos: Tomemos la red $\mathbb{Z}^2$ y trasladar el cubo unitario $[0,1]^2$ a lo largo de la línea que pasa por el origen con alcance irracional, obteniendo así una franja. Consideremos todas las aristas de $\mathbb{Z}^2$ que yacía dentro de la tira. Entonces la secuencia de aristas verticales y horizontales es una secuencia cuasiperiódica. Véase, por ejemplo http://arxiv.org/pdf/cond-mat/9903010v1.pdf fig.4.2 para el caso de una sucesión de Fibonacci (pendiente = proporción áurea 0,618...).

Así, para comprobar si una palabra es una subpalabra de la palabra Fibonacci, basta con "elevarla" a un camino en el grafo de aristas de $\mathbb{Z}^2$ y comprobar si está contenida en una franja de pendiente de razón áurea y anchuras correspondientes (por ejemplo, proyectando ortogonalmente).

Incluso se puede ampliar este método para obtener la frecuencia (asintótica) de la subpalabra en la palabra de Fibonacci, que es proporcional a la diferencia de la longitud de la proyección ortogonal de la subpalabra respecto a la longitud de la proyección de la banda (es decir, = longitud de proyección del cuadrado unitario por definición). El caso más fácil son, por supuesto, las dos parcelas de construcción de la secuencia, que se elevan a un borde vertical resp. horizontal de la red. Por lo tanto, la proporción de la frecuencia de aparición es de nuevo la proporción áurea. Pero se puede calcular inmediatamente de la misma manera la de la frecuencia de cualquier subpalabra.

Answer 4

Existe un sencillo algoritmo para determinar el conjunto de palabras que no aparecen como factores (subpalabras) en la palabra Fibonacci $f$ (que procede esencialmente de la caracterización que Ale De Luca señalaba en su pregunta).

Tomemos la secuencia de Fibonacci $(F_n)_{n\geq 0}=1,1,2,3,5,8,\ldots$ . Para cada $n$ mayor que $1$ toma la palabra de longitud $F_n-2$ que aparece al principio de la palabra Fibonacci $f$ (es decir prefijo de $f$ de longitud $F_n-2$ ). Esto le da la secuencia de palabras $\lambda,0,010,010010,\ldots$ Ahora, para cada una de estas palabras $v$ si $v$ va seguido del símbolo $1$ entonces toma $0v0$ ; en caso contrario, si $v$ va seguido del símbolo $0$ entonces toma $1v1$ . Así se obtiene el conjunto de palabras de longitud mínima que no aparecen como factores en $f$ es decir, los factores mínimos prohibidos de $f$ : $11,000,10101,00100100,\ldots$

Las palabras que no aparecen como subpalabras en la palabra Fibonacci $f$ son precisamente las palabras sobre $\{0,1\}$ que contengan un factor mínimo prohibido.

Answer 5

No sé si hay una caracterización sencilla, pero parece que hay un algoritmo sencillo. Véase Bartosz Walczak, A simple representation of subwords of the Fibonacci word, disponible en http://tcs.uj.edu.pl/~walczak/fibonacci.pdf