Idiomas que no podemos (des) probar que no tienen contexto

21

Estoy buscando idiomas que "probablemente no estén libres de contexto" pero no podemos (des) probarlo usando técnicas estándar conocidas.

¿Hay una encuesta reciente sobre el tema o una sección de problemas abierta de una conferencia reciente?

Probablemente no haya muchos idiomas que no se sepa que son CF, por lo que si conoce uno también puede publicarlo como respuesta.

Los ejemplos que encontré son:

Nota : como lo muestra Aryeh en su respuesta, puede construir una clase completa de dichos lenguajes si "vincula" un lenguaje a una conjetura desconocida sobre la (no) finitud o (no) vacío de algunos conjuntos (por ejemplo, no puede expresarse como una suma de dos primos ). No estoy muy interesado en tales ejemplos.LGoldbach={12n2n}

Marzio De Biasi
fuente
1
Para su segundo ejemplo, escribí un artículo de mi respuesta que está bajo revisión (y la primera respuesta fue positiva): arxiv.org/abs/1901.03913
domotorp
Hay muchas variantes del primer ejemplo que no se sabe que están libres de contexto, no sé si desea incluirlas como ejemplos separados; ver el Capítulo 10 del libro vinculado (Teoría Kászonyi-Katsura).
domotorp
@domotorp: Acabo de echarle un vistazo (todavía estoy leyendo el capítulo 2) ... me parecen más intentos técnicos para atacar el problema principal.
Marzio De Biasi

Respuestas:

14

Otra buena es el complemento del conjunto S de subpalabras contiguas (también conocidos como "factores") de la secuencia Thue-Morse t=0110100110010110 . Para dar un poco de contexto, Jean Berstel demostró que el complemento del conjunto T de prefijos de la palabra Thue-Morse no tiene contexto (y en realidad es algo más general que eso). Pero el resultado correspondiente para las subpalabras todavía está abierto.

Jeffrey Shallit
fuente
¡Muchas gracias! Si lo vio en algún lugar (¿tal vez en uno de sus muchos documentos sobre la secuencia Thue-Morse? ;-) puede agregar la referencia (incluso si se indica en el formulario de morfismo iterado).
Marzio De Biasi
12

¿Qué tal el lenguaje LTP de primos gemelos? Es decir, todos los pares de números naturales (p,p) (representados, digamos, en unario), de modo que p,p son primos y p=p+2 ? Si la conjetura de primos gemelos es verdadera, entonces LTP no está libre de contexto; de lo contrario, es finito.

Editar: Permítanme dar un bosquejo de prueba rápida de que la conjetura de los primos gemelos implica que LTP no está libre de contexto. Asociado a cualquier idioma L su secuencia de longitud 0a1a2 , donde el entero aparece en la secuencia si y sólo si hay una palabra de longitud en L . Es una consecuencia de los lemas de bombeo que para L que son regulares o CFL, la secuencia de longitud satisface la propiedad de diferencias limitadas: hay un R>0 tal que an+1anRpara todon. Es un hecho fácil y bien conocido en la teoría de números que los números primos no tienen diferencias acotadas. Finalmente, cualquier subsecuencia infinita de una secuencia que viole la propiedad de diferencias limitadas en sí misma debe violarla.

Aria
fuente
3
¡Genial gracias! Pero no estoy muy interesado en los lenguajes que están vinculados a conjeturas desconocidas sobre la (no) finitud de algunos conjuntos. Por cierto, si esas conjeturas son ciertas, el lenguaje resultante también es regular :-)
Marzio De Biasi
Si hay infinitos primos gemelos, ¿cómo ves que es regular? LTP
Aryeh
1
Si hay infinitos primos gemelos, ¿cómo demuestra que no está libre de contexto? LTP
Emil Jeřábek apoya a Mónica el
1
Oh, lo siento, no me di cuenta de que representas los números en unario. Entonces está claro. (Creo que probar esto para la representación binaria requeriría un progreso considerable en la conjetura de los primos gemelos.)
Emil Jeřábek apoya a Mónica el
55
Por el contrario, Emil, la prueba "estándar" de que los primos en binario no están libres de contexto es suficiente para demostrar que cada conjunto infinito de primos no está libre de contexto. Entonces, si hay infinitos primos gemelos, el resultado es inmediato.
Jeffrey Shallit