problema de separar palabras

Problema no resuelto en informática :

¿Cuántos estados se necesitan en un autómata finito determinista que se comporta de manera diferente en dos cadenas dadas de longitud $n$ ?

(más problemas sin resolver en informática)

En informática teórica , el problema de la separación de palabras es el problema de encontrar el autómata finito determinista más pequeño que se comporte de manera diferente en dos cadenas dadas , lo que significa que acepta una de las dos cadenas y rechaza la otra. Es un problema abierto el tamaño que debe tener dicho autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada.

Ejemplo

Las dos cadenas 0010 y 1000 pueden distinguirse entre sí mediante un autómata de tres estados en el que las transiciones desde el estado inicial van a dos estados diferentes, ambos terminales en el sentido de que las transiciones posteriores desde estos dos estados siempre regresan a el mismo estado. El estado de este autómata registra el primer símbolo de la cadena de entrada. Si uno de los dos estados terminales acepta y el otro rechaza, entonces el autómata aceptará sólo una de las cadenas 0010 y 1000. Sin embargo, estas dos cadenas no pueden ser distinguidas por ningún autómata con menos de tres estados. ^[1]

Supuestos simplificadores

Para demostrar los límites de este problema, se puede suponer sin pérdida de generalidad que las entradas son cadenas sobre un alfabeto de dos letras. Porque, si dos cadenas de un alfabeto más grande difieren, entonces existe un homomorfismo de cadena que las asigna a cadenas binarias de la misma longitud que también difieren. Cualquier autómata que distinga las cadenas binarias se puede traducir en un autómata que distinga las cadenas originales, sin ningún aumento en el número de estados. ^[1]

También se puede suponer que las dos cuerdas tienen la misma longitud. Para cadenas de longitud desigual, siempre existe un número primo $p$ cuyo valor es logarítmico en la menor de las dos longitudes de entrada, de modo que las dos longitudes son diferentes módulo $p$ . En este caso, se puede utilizar un autómata que cuente la longitud de su módulo de entrada $p$ para distinguir las dos cadenas entre sí. Por lo tanto, las cadenas de longitudes desiguales siempre se pueden distinguir entre sí mediante autómatas con pocos estados. ^[1]

Historia y límites

El problema de acotar el tamaño de un autómata que distingue dos cadenas dadas fue formulado por primera vez por Goralčík y Koubek (1986), quienes demostraron que el tamaño del autómata es siempre sublineal. ^[2] Posteriormente, Robson (1989) demostró el mejor límite superior conocido, $O (n 2/5 (log n) 3/5)$ , sobre el tamaño del autómata que puede ser requerido. ^[3] Chase (2020) mejoró esto a $O (n 1/3 (log n) 7)$ . ^[4]

Existen pares de entradas que son cadenas binarias de longitud $n$ para las cuales cualquier autómata que distinga las entradas debe tener un tamaño $Ω(log n)$ . Cerrar la brecha entre este límite inferior y el límite superior de Chase sigue siendo un problema abierto. ^[1] Jeffrey Shallit ha ofrecido un premio de 100 libras esterlinas por cualquier mejora en el límite superior de Robson. ^[5]

Casos especiales

Se sabe que varios casos especiales del problema de separación de palabras se pueden resolver utilizando pocos estados:

Si dos palabras binarias tienen diferentes números de ceros o unos, entonces se pueden distinguir entre sí contando sus pesos de Hamming módulo primo de tamaño logarítmico, utilizando un número logarítmico de estados. De manera más general, si un patrón de longitud $k$ aparece un número diferente de veces en las dos palabras, se pueden distinguir entre sí usando estados $O (k log n) .$ ^[1]
Si dos palabras binarias difieren entre sí dentro de su primera o última $k$ posiciones, se pueden distinguir entre sí usando $k + O (1)$ estados. Esto implica que casi todos los pares de palabras binarias se pueden distinguir entre sí con un número logarítmico de estados, porque sólo una fracción polinomial pequeña de pares no tienen diferencias en sus posiciones $O (log n) iniciales.$ ^[1]
Si dos palabras binarias tienen una distancia de Hamming $d$ , entonces existe un primo $p$ con $p = O (d log n)$ y una posición $i$ en la que las dos cadenas difieren, de modo que $i$ no es igual en módulo $p$ a la posición de cualquier otra diferencia. . Al calcular la paridad de los símbolos de entrada en posiciones congruentes con $i$ módulo $p$ , es posible distinguir las palabras usando un autómata con estados $O (d log n) .$ ^[1]

Referencias

^ abcdefg Demaine, Erik D .; Eisenstat, Sarah; Shalit, Jeffrey ; Wilson, David A. (2011), "Observaciones sobre la separación de palabras", Complejidad descriptiva de sistemas formales: 13º taller internacional, DCFS 2011, Gießen/Limburg, Alemania, 25 al 27 de julio de 2011, Actas , Apuntes de conferencias en informática, vol. 6808, Heidelberg: Springer-Verlag, págs. 147–157, arXiv : 1103.4513 , doi : 10.1007/978-3-642-22600-7_12, MR 2910373, S2CID 6959459.
^ Goralčík, P.; Koubek, V. (1986), "Sobre el discernimiento de palabras mediante autómatas", Autómatas, lenguajes y programación: 13º Coloquio Internacional, Rennes, Francia, 15 al 19 de julio de 1986, Actas , Lecture Notes in Computer Science, vol. 226, Berlín: Springer-Verlag, págs. 116–122, doi :10.1007/3-540-16761-7_61, MR 0864674.
^ Robson, JM (1989), "Separación de cadenas con pequeños autómatas", Cartas de procesamiento de información , 30 (4): 209–214, doi :10.1016/0020-0190(89)90215-9, MR 0986823.
^ Chase, Z. (2020), "Un nuevo límite superior para separar palabras", arXiv : 2007.12097 [math.CO].
^ Shallit, Jeffrey (2014), "Problemas abiertos en la teoría de los autómatas: una visión idiosincrásica", Coloquio británico de informática teórica (BCTCS 2014), Universidad de Loughborough (PDF).