Problema en informática teórica
Problema sin resolver 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 ?
En informática teórica , el problema de separar 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 , es decir, que acepte una de las dos cadenas y rechace 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 pasan a dos estados diferentes, ambos terminales en el sentido de que las transiciones posteriores desde estos dos estados siempre vuelven al 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 es de aceptación y el otro de rechazo, entonces el autómata aceptará solo una de las cadenas 0010 y 1000. Sin embargo, estas dos cadenas no pueden distinguirse mediante ningún autómata con menos de tres estados. [1]
Simplificando suposiciones
Para probar 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 sobre un alfabeto más grande difieren, entonces existe un homomorfismo de cadenas que las asigna a cadenas binarias de la misma longitud que también difieren. Cualquier autómata que distinga las cadenas binarias puede traducirse 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 cadenas tienen la misma longitud. Para cadenas de longitudes diferentes, 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 entrada módulo p para distinguir las dos cadenas entre sí. Por lo tanto, las cadenas de longitudes diferentes siempre se pueden distinguir entre sí mediante autómatas con pocos estados. [1]
Historia y límites
El problema de limitar 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] Más tarde, Robson (1989) demostró el límite superior O ( n 2/5 (log n ) 3/5 ) sobre el tamaño del autómata que puede requerirse. [3] Esto fue mejorado por Chase (2020) a O ( n 1/3 (log n ) 7 ) . [4] [5]
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. Jeffrey Shallit ha ofrecido un premio de 100 libras esterlinas por cualquier mejora en el límite superior de Robson. [6]
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 cantidades de ceros o unos, se pueden distinguir entre sí contando sus pesos de Hamming módulo un 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í utilizando O ( k log n ) estados. [1]
- Si dos palabras binarias difieren entre sí en sus primeras o últimas k posiciones, se pueden distinguir entre sí utilizando 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 solo una fracción polinomialmente pequeña de pares no tienen diferencias en sus posiciones iniciales O (log n ) . [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 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 utilizando un autómata con O ( d log n ) estados. [1]
Referencias
- ^ abcdef Demaine, Erik D. ; Eisenstat, Sarah; Shallit, Jeffrey ; Wilson, David A. (2011), "Observaciones sobre la separación de palabras", Complejidad descriptiva de sistemas formales: 13.º taller internacional, DCFS 2011, Gießen/Limburgo, Alemania, 25-27 de julio de 2011, Actas , Lecture Notes in Computer Science, vol. 6808, Heidelberg: Springer-Verlag, págs. 147–157, arXiv : 1103.4513 , doi :10.1007/978-3-642-22600-7_12, ISBN 978-3-642-22599-4, MR 2910373, S2CID 6959459.
- ^ Goralčík, P.; Koubek, V. (1986), "Sobre el discernimiento de palabras por autómatas", Automata, Languages and Programming: 13th International Colloquium, Rennes, Francia, 15-19 de julio de 1986, Actas , Lecture Notes in Computer Science, vol. 226, Berlín: Springer-Verlag, pp. 116-122, doi :10.1007/3-540-16761-7_61, ISBN 978-3-540-16761-7, Sr. 0864674.
- ^ Robson, JM (1989), "Separación de cadenas con pequeños autómatas", Information Processing Letters , 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].
- ^ Chase, Zachary (15 de junio de 2021). "Separación de palabras y reconstrucción de trazas". Actas del 53.º Simposio anual ACM SIGACT sobre teoría de la computación . STOC 2021. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 21–31. doi :10.1145/3406325.3451118. ISBN 978-1-4503-8053-9.
- ^ Shallit, Jeffrey (2014), "Problemas abiertos en la teoría de autómatas: una visión idiosincrásica", Coloquio británico sobre informática teórica (BCTCS 2014), Universidad de Loughborough (PDF).
