Cubo libre de binario infinito palabras

Question

Una palabra $y$ es un subword de $w$ si existen palabras $x$ e $z$ (posiblemente vacía) de forma tal que $w=xyz$. Por lo tanto, $01$ es un subword de $0110$, pero $00$ no es un subword de $0110$. Estoy interesado en el derecho infinito de palabras de más de dos letras del alfabeto que no contienen subpalabras de la forma $xxx$ donde $x$ es una palabra de una o más letras. (Por ejemplo, la Thue-Morse palabra, la Kolakoski palabra, Stewart coral de la secuencia, y así sucesivamente.) En particular, me gustaría saber si hay alguna de las declaraciones generales acerca de todas esas palabras. Por ejemplo, hay un número infinito de ellos? Es allí cualquier manera de clasificarlos?

Es posible que una forma de clasificar cubo libre de binario infinito palabras es agruparlos de acuerdo a sus subpalabras. Por ejemplo, el Kolakoski palabra tiene la subword $00100$, mientras que el Thue-Morse palabra no, por lo que pertenecen a clases diferentes. Las palabras creadas en Tony respuesta (ver más abajo) tienen el mismo subpalabras (el Thue-Morse palabra es recurrente), por lo que pertenecen a una clase. Supongo que habrá un número infinito de estas clases.

Otra posible forma de clasificar cfib palabras es agruparlos de acuerdo a sus subword complejidad. Por ejemplo, Stewart coral de la secuencia tiene un subword complejidad de $2n$ (donde $n$ es la longitud de la subword), por lo que puede agrupar con otros cfib palabras con subword la complejidad de la $2n$. Es el subword complejidad de la Kolakoski palabra conocida?

Answer 1

Hasta donde yo sé, no se conoce la caracterización de cubo libre de binario infinito de palabras. Sin embargo, una manera de generar este tipo de palabras es mediante la iteración de los llamados cubo binarias libres de morfismos, es decir, endomorphisms en un alfabeto binario que preservar cubo libre binario finito de palabras. La familia de todos los morfismos ha sido caracterizada; véase, por ejemplo, el papel por Richomme & Wlazinski (2002) y las referencias allí contenidas. Tenga en cuenta que existen binario morfismos que no se cubo libre, sino generar un cubo libre de binario infinito de palabras. Richomme & Wlazinski (2002) proporciona un ejemplo de este tipo de morfismos. También resultó una nueva caracterización de los morfismos de una forma particular que generan cubo libre de binario infinito palabras y demostró que esta caracterización proporciona un método más eficaz de determinar si una determinada binario de morfismos genera un cubo libre de infinito palabra en comparación con el original de la caracterización de tales morfismos obtenidos por Karhumäki (1983). Las referencias en Richomme & Wlazinski del papel debe ser de ayuda para usted.

Answer 2

Aquí están algunas profunda de los hechos relativos a binario cfw:

1) El conjunto de la derecha infinito binario cubo libre de palabras es un conjunto perfecto en el sentido topológico: Para cualquier secuencia de este, hay una diferencia de uno que está de acuerdo con que a la enésima carta. En particular, hay una cantidad no numerable de binario de cfw.

2) Dado cualquier finito secuencia binaria, es decidable si se extiende a una infinita binario cubo-free word.

3) El número de (finito) binario de cfw de longitud n crece exponencialmente con n.

Estos resultados (y de forma análoga para el k-libre del poder de las palabras a lo largo de diversos alfabetos) se demuestran en el

http://dl.acm.org/citation.cfm?id=873885 y http://www.sciencedirect.com/science/article/pii/0195669895900519

Answer 3

Hay un número infinito de cubo binarias libres de palabras. Deje $w$ ser uno de esos palabra (como el Thue-Morse de la palabra). Deje $w-j$ denotar la palabra obtenido al eliminar la primera $j$ cartas de $w$. Claramente, para todos los $j \in \mathbb{N}$, $w-j$ es también el cubo de forma gratuita. Además, afirmo que la $w-j \neq w-k$ cualquier $j < k$, a partir de la cual el resultado de la siguiente manera. Hacia una contradicción, supongamos que $w-j=w-k$ para algunos $j < k$. Deje $w=abc$ donde $a$ tiene una longitud de $j$ e $b$ tiene una longitud de $k-j$. A continuación, $bc=c$ por hipótesis. La iteración, podemos ver que $c$ comienza con $bbb$, contradiciendo ese $w$ es el cubo libre.

Answer 4

Lema: Alguien capaz de hablar de una infinita cubefree palabra puede transmitir información de, al menos, $1/24$ de la velocidad de una persona común, capaz de hablar de un arbitrario secuencia binaria.

Prueba: Considere el siguiente período-$12$ secuencia en el alfabeto $\{ 0, 1, ?\}$:

$S = (001?010?1011)^{\infty}$

Ahora supongamos $T$ es una secuencia derivada de $S$ mediante la sustitución de cada una de las $?$ con $0$ o $1$.

• $T$ claramente no tiene las palabras de la forma $xxx$ para un solo dígito $x$.

Si tomamos la alternativa dígitos en $T$, obtenemos $(010011)^{\infty}$. La única cubos en esta secuencia tiene una longitud múltiplo de $6$, por lo tanto:

• Si $T$ contiene una palabra de la forma $WWW$ donde $W$ incluso ha de longitud, a continuación, $W$ tiene una longitud múltiplo de 12.

• También, $T$ contiene una palabra de la forma $WWW$ donde $W$ tiene una longitud de $3$ si y sólo si dos signos de interrogación en la misma dodecad $(001?010?1011)$ son ambos cero. Afirman que esto no va a suceder.

• Si $T$ contiene una palabra de la forma $WWW$ donde $W$ tiene una longitud múltiplo de $3$,, a continuación, $W$ tiene una longitud múltiplo de $12$.

Por lo tanto sólo estamos preocupados acerca de las palabras de longitud coprime o divisible por $12$.

• Si la longitud de $W$ es $\pm 1 \mod 12$, entonces la existencia de $WWW$ es descartado por la prueba de la no existencia de $xxx$.

• Del mismo modo, es fácil observar que no hay ninguno de longitud $\pm 5 \mod 12$.

Por lo que cualquier palabra de la forma $WWW$ en $T$ requiere $W$ a tiene longitud divisible por $12$.

---

Ahora a comenzar con cualquier tripleless secuencia de más de $\{A, B\}$ (tales como la Thue-Morse secuencia) y aplicar las reglas de sustitución:

$A \mapsto (001001011011)$

$B \mapsto (0011010?1011)$

Entonces obtendremos una infinita palabra sobre $\{0, 1, ?\}$ tal forma que:

• Cada reemplazo de los signos de interrogación con los dígitos de los rendimientos de un infinito cubefree palabra.
• Cada icositetrad contiene un signo de interrogación.

El resultado de la siguiente manera.