Problema de separación de palabras

En informática teórica , el problema de la separación de palabras consiste en encontrar el autómata finito determinista más pequeño que se comporte de manera diferente ante dos cadenas dadas , es decir, que acepte una de las dos cadenas y rechace la otra. Aún se desconoce el tamaño mínimo que debe tener dicho autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada.

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 conducen a dos estados diferentes, ambos terminales en el sentido de que las transiciones subsiguientes desde estos dos estados siempre regresan 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 ]}

Para demostrar límites en este problema, se puede suponer, sin pérdida de generalidad, que las entradas son cadenas sobre un alfabeto de dos letras. Pues, si dos cadenas sobre un alfabeto mayor difieren, existe un homomorfismo de cadenas que las transforma en 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 aumentar el número de estados. ^{[ 1 ]}

También se puede suponer que las dos cadenas 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 entrada módulo p para distinguir las dos cadenas entre sí. Por lo tanto, las cadenas de longitud desigual siempre se pueden distinguir entre sí mediante autómatas con pocos estados. ^{[ 1 ]}

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 siempre es sublineal. ^{[ 2 ]} Posteriormente, Robson (1989) demostró la cota superior O ( n ^2/5 (log n ) ^3/5 )  para el tamaño del autómata que puede ser necesario. ^{[ 3 ]} Esto fue mejorado por Chase (2020) a O ( n ^1/3 (log n ) ⁷ )  . ^{[ 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 de Ω(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 al límite superior de Robson. ^{[ 6 ]}

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

• Si dos palabras binarias tienen diferente número 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 forma 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, pueden distinguirse entre sí utilizando k + O (1) estados. Esto implica que casi todos los pares de palabras binarias pueden distinguirse entre sí con un número logarítmico de estados, ya que solo una fracción polinómicamente pequeña de pares no presenta diferencias en sus O (log n ) posiciones iniciales. ^{[ 1 ]}
• Si dos palabras binarias tienen una distancia de Hamming d , entonces existe un primo p tal que 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 ninguna 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 ]}