Secuencias periódicas en alfabeto finito

Question

Deje $\Sigma=\{A,B,C\}$ ser un alfabeto, y deje $\Sigma^{\mathbb{N}}$ el conjunto de secuencias infinitas en $\Sigma$ (ie $ABCBCCCBABC...$). Por las condiciones en el exterior, tengo varios subsecuencias que no están permitidos, a saber,$AA, BB, CC, ABAB, ACAC, BABA, BCBC, CACA, CBCB, ACB, BAC, CBA$, y quiero demostrar que todos los $\sigma\in\Sigma^{\mathbb{N}}$ son finalmente periódico. Me gustaría saber si hay alguna de los resultados sobre este tema o cualquier sugerencias de maneras de proceder en una prueba.

Los intentos anteriores: Mi idea original era que se podía crear un contraejemplo al hacer bloques de longitud 3 que representan el 0 y 1 y, a continuación, crear una especie de irracional decimal con estos (decir $\pi$ en binario, por ejemplo). Me fui a través de las combinaciones admisibles y encontró que esto era imposible. Haciendo esto de nuevo para grandes bloques parece posible, pero me gustaría encontrar algunos resultados generales sobre este problema.

(Disculpas por las etiquetas, no puedo entender qué buenos son para esta pregunta.)

Answer 1

Puedo ver un ataque de fuerza bruta enfoque para (intentar) lo demuestran. Asumir su infinita secuencia comienza de CA. El siguiente término debe ser, así que ACA. El siguiente término debe ser B, por lo que ACAB. Ahora empieza a ser complicado. Parece que el 5º término puede ser a o C, pero si se utiliza Un después no válido 6 de plazo, por lo que, de hecho, el 5 de término debe ser C, por lo que ACABC. El 6 de plazo podría ser a o B, pero B no válida 7 de plazo, por lo que ACABCA. El 7 de plazo podría ser B o C, pero C no válidos 8 de plazo, por lo que ACABCAB. Ahora estamos de vuelta a donde estábamos, después de 4 términos, por lo que debemos repetir la CABINA para siempre de aquí en adelante.

Así que cuida de secuencias a partir de CA. Tienes 8 otros casos a tratar (bueno, 5, desde AA, BB y CC son no-arrancadores).

Answer 2

Edificio en Gerry Myerson la respuesta...

El conjunto de prohibido subsecuencias es estable bajo las sustituciones dado por el 3-ciclo de $\tau=(ACB)$. En otras palabras, si $X_1X_2\ldots X_k$ está prohibido, entonces también lo es $\tau(X_1)\tau(X_2)\ldots\tau(X_k)$. Por lo tanto los 5 casos restantes comprimir a 1: dos de ellos están en la órbita de la secuencia inicial $AC$ manejado por Gerry, y los tres restantes forman otra órbita.

Vamos a escoger la secuencia inicial $AB$ a partir de que otra órbita. No puede continuar con $B$. Si la tercera carta se $A$, entonces no habría alternativas legales para la cuarta, por lo que la secuencia debe comenzar a $ABC$. Aquí el último par de $BC=\tau^2(A)\tau^2(B)$, por lo que el mismo argumento (se aplican $\tau^2$ a la anterior) de las fuerzas de la próxima carta a los ser $\tau^2(C)=A$, y es el que va cíclicamente: la única alternativa para la siguiente letra es obtenido de la anterior por la aplicación de $\tau^2$. Como $\tau$ es de orden 3, obtenemos la repetición del ciclo de longitud 3.

Answer 3

Aquí hay un poco menos de fuerza bruta enfoque que proporciona un poco diferente punto de vista. Dado un válido secuencia infinita, es claro que cada uno de $A$, $B$, $C$ se produce infinitamente a menudo. Comprobamos que la distancia entre dos apariciones consecutivas de $A$ es en la mayoría de las $3$ (donde la distancia se calcula coordinar sabio, así, por ejemplo, la distancia entre el $A$s en $ABCBAB$$4$). Si la distancia entre dos consecutivos $A$s es $4$, entonces a partir de la $BB$ $CC$ no están permitidas, la configuración debe ser uno de $ABCBA$$ACBCA$, ninguno de los cuales es válida. Si la distancia entre dos consecutivos $A$s es mayor que $4$, luego entre ellos debe ocurrir uno de $BB$, $CC$, $BCBC$, y $CBCB$, por lo que no es bueno tampoco.

Por simetría, la distancia entre dos consecutivos $A$s, $B$s o $C$s es en la mayoría de las $3$. Pero después de cada letra se ha producido al menos una vez, esta distancia no puede ser $2$ (u obviamente $1$). Si la distancia entre dos $A$s es $2$, entonces hay algunas carácter único entre ellos (es decir $B$). Pero entonces la distancia entre el $C$ antes de esta configuración y el $C$ después de por lo menos es $4$, que sabemos que es imposible.

Por lo tanto, más allá de un cierto punto, la distancia entre dos apariciones consecutivas de un mismo personaje es exactamente $3$, con lo que la secuencia eventualmente periódico.

Answer 4

El uso de Gerry Myerson la idea de la fuerza bruta, me escribió un (Python), programa para hacer exactamente eso. Lo que he encontrado es que en realidad se está correcta; todas las infinitas secuencias son periódicas. Sólo si permite secuencias finitas ¿no-periódicas de las secuencias, pero en todos los casos, es el último personaje que rompe con la periodicidad. También, la periodicidad es siempre de la forma "...ABCABCABC...". Esperemos que eso sea suficiente para alguien que le dé un carácter más abstracto de la prueba.

Y, para los curiosos, aquí está mi código:

def do(l, s, d, a, infin = 1):

    win = []

    if len(s) > l:
        for i in xrange(1, len(s)/2):
            if s[-i:] == s[-i*2:-i] or (infin and i<len(s)/2 and s[-i-1:-1] == s[-i*2-1:-i-1]):
                return []
        return [s]

    for k in a:

        s2 = s + k
        nope = 0

        for j in d:
            if len(s2) >= len(j) and s2[-len(j):] == j:
                nope = 1

        if nope == 0:
            win.extend(do(l, s2, d, a, infin))

    return win

def run(length, infin, start = "", disallowed="AA,BB,CC,ABAB,ACAC,BABA,BCBC,CACA,CBCB,ACB,BAC,CBA", add="A,B,C"):
    d = disallowed.split(",")
    a = add.split(",")
    win = []
    for i in a:
        s = start+i
        win.extend(do(length, s, d, a, infin))
    return win

la longitud se establece el punto de corte para la distancia a la apariencia y configuración de infin a $0$ efectivamente hace de verificación de secuencias infinitas.

Answer 5

Se ha visto que las restricciones son cíclicamente-invariante, por lo que es mejor para especificar la secuencia de símbolos $\{A,B,C\}$ el uso de algunos "delta" código: di $\{-, =, +\}$ donde $+$ significa "cambio para el símbolo a la derecha" (cíclicamente) ($A \to B$, $B \to C$, $C \to A$), $=$ significa "repetir el mismo símbolo", $-$ significa "símbolo a la izquierda". Esto (junto con el primer símbolo) totalmente especifica cualquier secuencia. Por ejemplo, en lugar de $ABBCBAC$ le gustaría escribir $A+=+--$

En realidad los tres primeros desestimado subsecuencias (AA, BB, CC), implícitamente, no permitir la $=$ símbolo (repeticiones está prohibido), por lo que podemos limitarnos a $\{- +\}$ o $\{0,1\}$.

El resto de las restricciones de no permitir las siguientes subsecuencias:

$ ABAB, BCBC, CACA \equiv 101$

$ ACAC, BABA, CBCB \equiv 010$

$ CBA, BAC, ACB \equiv 00$

Así que nos quedamos con el sencillo problema de la construcción de una secuencia de $\{0,1\}$ con las subsecuencias $00, 010, 101$ desestimado. Es fácil ver que el único permitido secuencias infinitas son:

$11111 \cdots$ $011111 \cdots$

Así que, después de los primeros dos símbolos, la secuencia se repita cíclicamente "a la derecha" ( ....ABCABCABC...)

Específicamente la única manera posible de secuencias infinitas son

ABCABCABC....   (A111111....)

BCABCABC....    (B111111....)

CABCABC....     (C111111....)

ACABCABC....    (A0111111....)

BABCABCABC....  (B0111111....)

CBCABCABC....   (C0111111....)