19 votos

Tres mitades libre de palabras (de forma análoga a la plaza libre)

Una plaza libre de palabra es una cadena de símbolos (una "palabra") que evita el patrón de $XX$ donde $X$ es cualquier consecutivos de la secuencia de símbolos en la cadena. Para un alfabeto de dos símbolos, el más largo de la plaza libre de palabra de longitud $3$. Pero para alfabetos de tres símbolos, hay infinitamente largo plaza libre de palabras, debido a Thue.

Definir un tres mitades-free word como uno que evita el patrón de $XYX$ donde $|X|=|Y|$. Otro punto de vista es que estas palabras evite $Z(\frac{1}{2}Z)$, es decir, $Z=XY$ con $X$ e $Y$ el longitud de la misma. Por lo $Z$ incluso ha de longitud, y queremos evitar de inmediato siguiendo con la primera mitad de $Z$.

Para un alfabeto de dos símbolos, $0$ & $1$, aquí están las tres mitades libre de palabras de longitud $5$: \begin{eqnarray*} &(0, 1, 1, 0, 0)\\ &(0, 0, 1, 1, 0)\\ &(1, 1, 0, 0, 1)\\ &(1, 0, 0, 1, 1) \end{eqnarray*} Todas las $28$ otros longitud-$5$ faltan las palabras. E. g., $(0,1,0,1,0)$ falla debido a $(0,1,0)$ de coincidencia con $XYX=010$. Pero no hay tres mitades libre de palabras de longitud $\ge 6$. Por ejemplo, la ampliación de $(0, 1, 1, 0, 0)$ con $0$ da $(0, 1, 1, 0, 0, 0)$, coincidente $XYX=000$, y se extiende con $1$ da $(0, 1, 1, 0, 0, 1)$, coincidente con $X=01$.

Q. Hay infinitamente larga palabras de tres letras de un alfabeto que son tres mitades libre?

Si una palabra tiene un cuadrado de $ZZ$ con $|Z|$, incluso, después de tres mitades patrón. Si una palabra es una plaza libre, no puede ser de tres mitades libre. Por ejemplo, $(1,0,1)$ e $(0,1,2,1,0,1)$ son cuadrados libres. Y la plaza libre de infinito palabra A029883 $$ (1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, \ldots ) $$ no es de tres mitades libre: por ejemplo, $(-1,1,-1)$ e $(-1,0,1,0,-1,0)$ son tres mitades de los patrones.

12voto

Zach Burlingame Puntos 7232

Fuerte de una propiedad es verdadera para cuatro-letra de los alfabetos. Que es, en Palabras sin casi repeticiones, Currie y Bendor-Samuel demostrar que no es un infinito de la palabra $\omega$ sobre un alfabeto de cuatro letras tal que siempre que $XYX$ se produce como un subword de $\omega$, $|Y| > |X|$. También demostrar que no es infinito palabra de tres letras del alfabeto con esto más fuertes de la propiedad.

11voto

Diondon Puntos 1

Nota: Este es un comentario extendido, no es una respuesta completa.

Yo no sé ustedes, pero yo no empecé con cualquier buena intuición sobre la respuesta a la pregunta. Me decidí a hacer algunos experimentos informáticos y de visualización.

Escribí el código en Prolog que genera plaza libre y tres mitades libre de palabras sobre un alfabeto. Yo normalmente no uso de Prolog para nada, pero este parecía el tipo de problema que es muy adecuado para. Código fuente y un entorno interactivo está disponible aquí. (Por favor comente si no funciona, el enlace está muerto, etc.) Por favor experimento en su propio demasiado!

La consulta siguiente genera el tres mitades libre de palabras de longitud 5 sobre el alfabeto x,y. En el código que yo he llamado "sándwich " libre" en lugar de "tres mitades-gratis".

?- sandwich_free(L,[x,y],5).
L = [x, y, y, x, x] ;
L = [x, x, y, y, x] ;
L = [y, y, x, x, y] ;
L = [y, x, x, y, y] ;
false.

"?-" es el símbolo del sistema; las cuatro líneas siguientes son los resultados, y "false" indica que no hay más respuestas. (El orden de los resultados es lexicográfica, si usted lee cada resultado de derecha a izquierda.)

Si usted pide el sandwich libre de palabras de longitud 6 sobre el mismo alfabeto, se obtiene 0 resultados:

?- sandwich_free(L,[x,y],6).
false.

He aquí un sándwich libre de palabra de longitud de 500 de más de un 3 letras del alfabeto:

?- sandwich_free(L,[x,y,z],500).
L = [y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, z, x, x, y, y, x, z, y, x, x, y, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x]
...

Usted puede pedir el sándwich libre de palabras de cualquier longitud a través de un determinado alfabeto:

?- sandwich_free_peano(L,[x,y],N).
L = [],
N = zero ;
L = [x],
N = s(zero) ;
L = [y],
N = s(zero) ;
L = [x, x],
N = s(s(zero)) ;
L = [y, x],
N = s(s(zero)) ;
L = [x, y],
N = s(s(zero)) ;
L = [y, y],
N = s(s(zero)) ;
L = [y, x, x],
N = s(s(s(zero)))
...

(Limitaciones técnicas en Prolog me obligó a escribir una versión independiente de sandwich_free el uso de Peano de los números, cuando estás pasando en un número no ya crear una instancia como una constante.)

También se puede utilizar para comprobar si una determinada lista de sándwich-libre:

?- sandwich_free_peano([x,y,z,z,y],[x,y,z],_).
true ;
false.

(La respuesta es verdadero; falso sólo indica que no hay más respuestas.)

Aquí está una parcela de largo vs el número de metros libre y sandwich libre de palabras de longitud de más de un 3-letra del alfabeto. El crecimiento parece ser exponencial:

Length vs. the number of square-free and sandwich-free words of that length over a 3-letter alphabet

La consulta que genera los puntos de datos se

?- numlist(0,23,L),maplist(how_many_sandwich_free_alphabet_3,L,XS).

Los puntos de datos en el gráfico son:

  • Plaza libre: 1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264, 342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418 (OEIS A006156)
  • Sándwich gratis: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008, 1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428, 86688, 128592 (no en la OEIS en este momento)

Esto me parece una evidencia convincente de que hay arbitrariamente largo, de tres mitades libre de palabras, de hecho exponencialmente muchos como una función de la longitud. También parece muy probable que infinitamente largo, de tres mitades libre de palabras existen.


Editar:

Aquí algunos interesantes datos nuevos: Decir que un sándwich libre de palabra es "extensible" si usted puede agregar una letra más al frente de ella para conseguir otro sándwich-free word. La mayoría de los sándwich libre de palabras son extensibles. Un ejemplo de una que no lo es:

_, y, y, x, x, y, z, z, x, x, z, y, y, x, x

Tratar de llenar el espacio en blanco en la parte delantera.

Más en general podemos hablar de "$k$-extensible" sándwich libre de palabras, por que me refiero a "$k$-extensible, pero no $(k+1)$-extensible". Ahora aquí está una parcela de cómo muchos no extensible y 1-extensible palabras hay de particular longitudes:

Length vs. the number of sandwich-free words, non-extensible sandwich-free words, and 1-extensible sandwich-free words, of that length over a 3-letter alphabet

(Datos: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008, 1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428, 86688, 128592, 190512, 282492, 418680, 620208, 919044, 1362456, 2012940; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 72, 72, 144, 396, 252, 396, 720, 1044, 1440, 2376, 3456, 5040, 7524, 11088, 16272, 26604, 36864; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36, 36, 72, 108, 180, 720, 540, 468)

11voto

Wancott Puntos 16

(No es una verdadera respuesta, sólo una conjetura)

Deje $w$ ser el Pansiot palabra en $4$ letras definidas aquí :
J. J. Pansiot, a propos d'une conjetura de F. Dejean sur les répétitions dans les mots, Discreta Matemática Aplicada, Volumen 7, número 3, Marzo de 1984, Páginas 297-311
en francés, o también en
J. Moulin Ollagnier, la Prueba de la Dejean la conjetura de alfabetos con 5, 6, 7, 8, 9, 10 y el 11 de letras, theoretical Computer Science, Volumen 95, número 2, De 30 de Marzo de 1992, Páginas 187-205.
Esta palabra demuestra Dejean la Conjetura de $4$ letras, que es:
evita fracciones de repeticiones de exponente mayor que $7/5$, y lo que es también de tres mitades libre.

$$w=abcdbadcbdacdbcadcbacdabdcadbcdacbadcabdacdbadcbdabcadbacdab...$$

Conjetura Teorema De

Deje $h(a)=aabbaccabc$, $h(b)=aacbacbacc$, $h(c)=abbaaccbbc$, $h(d)=abcaacbbcc$.

A continuación, $h(w)$ es de tres mitades-free word en $3$ letras.

He comprobado hasta el tamaño de 412030. Yo no trató de probar el resultado, pero tal vez la prueba es simple y "estándar" (supongamos que la imagen tiene tres mitades, luego de demostrar que la pre-imagen tiene tres reducir a la mitad).

editar: La prueba es fácil. $h$ es $10$-uniforme y es la sincronización, que es para todos los $x,y,z\in\{a,b,c,d\}$, $h(x)$ no es un buen infix de $h(yz)$. Por lo tanto, si un factor de $XYX$ de $h(w)$ es un tres-reducir a la mitad, entonces cualquiera de las $XYX$ es pequeña (del tamaño en la mayoría de los $18\times 3$) o $\vert X \vert = \vert Y \vert$ es un múltiplo de $10$. Hay sólo un número finito de "pequeño" factores de verificación.
Ahora, si estamos en el segundo caso, y si $\vert X \vert$ si grande (al menos $42$), a continuación, $XYX$ tiene un único de sustitución de en $w$, e $w$ tiene un factor de $X'Y'X'$ con $\vert Y' \vert / \vert X' \vert > 2/5$. Por lo tanto $w$ tiene una repetición de exponente mayor que $7/5$, y tenemos una contradicción con el hecho de que $w$ es un Dejean palabra (es decir, se $7/5+$-libre).

10voto

marcospereira Puntos 3144

También no es una respuesta, pero puede ser útil.

Algo similar tipo de palabra es mencionado al final de la sección 1.5 de Salomaa: Joyas del Lenguaje Formal de la Teoría:

Hay un infinito de la palabra más de un 3-letra del alfabeto de tal forma que cada "sandwich" $XYX$ (con $X$ vacío) en la palabra es bastante carnoso, viz., $|Y|\ge\frac13|X|$. También, $1/3$ es fuerte aquí como un nivel de carnosidad: a partir de la longitud de 39 cada palabra debe contener un sándwich de no más carnoso que el (que por cierto es evidencia anecdótica de que tenemos que mirar bastante largo palabras antes de sacar conclusiones en esta área).

Así, mientras que usted está preguntando si hay una infinita desequilibrado sándwich palabra ("equilibrado", es decir que la carne es tan grueso como cada bun), esto demuestra que hay una infinita carnoso sándwich de palabra.

8voto

Peanut Puntos 2345

Esta no es una respuesta, pero puede ayudar.

De acuerdo a Una generalización de la repetición umbral de Lucian Iliea, Pascal Ochemb, y Jeffrey Shallit (theoretical Computer Science, Tomo 345, Problemas de 2-3, 22 de noviembre de 2005, Páginas 359-369)

Brandenburg [3] y (implícitamente) Dejean [6] se considera el problema de la determinación de la la repetición de umbral; es decir, el menor exponente $\alpha=\alpha(k)$ tal de que existen infinitas palabras sobre $\Sigma_k$ que evite $(\alpha+\epsilon)$-de los poderes de todos los $\epsilon>0$. Dejean demostrado que $\alpha(3)=\frac74$.

(Dejean del papel es en francés, y yo no puedo leer en francés.)

Como Bjørn Kjos-Hanssen señala en un comentario, el resultado que se asienta citar el caso de la energía libre de palabras que evitar todos los poderes mayor o igual a 3/2, pero Joseph O'Rourke cuestión está pidiendo 3/2 libre de palabras. (Es posible que una palabra para ser 3/2-libre pero contienen poderes más grandes que los 3/2, por ejemplo, la palabra $00$ tiene un cuadrado y, sin embargo, es de 3/2 libre.)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X