Problema de separación de palabras

Problemas no resueltos de la computer science: How many states are needed in a deterministic finite automaton that behaves differently on two given strings of length n?

En la teoría computacional, el problema de separar palabras es el problema de encontrar el autómata finito determinista más pequeño que se comporta de manera diferente en dos cadenas dadas, lo que significa que acepta una de las dos cadenas y rechaza la otra. El tamaño que debe tener un autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada es un problema abierto.

Ejemplo

Las dos cadenas 0010 y 1000 pueden distinguirse entre sí por un autómata de tres estados en el que las transiciones desde el estado de inicio pasan a dos estados diferentes, ambos terminales en el sentido de que las transiciones posteriores de 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 está aceptando y el otro está rechazando, entonces el autómata aceptará solo una de las cadenas 0010 y 1000. Sin embargo, estas dos cadenas no pueden distinguirse por ningún autómata con menos de tres estados.

Simplificando suposiciones

Para probar los límites en 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 en un alfabeto más grande difieren, entonces existe un homomorfismo de cadena que las correlaciona con cadenas binarias de la misma longitud que también difieren. Cualquier autómata que distingue las cadenas binarias se puede traducir en un autómata que distingue las cadenas originales, sin ningún aumento en la cantidad 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. Un autómata que cuente la longitud de su entrada  módulo p se puede usar para distinguir las dos cadenas entre sí en este caso. Por lo tanto, las cadenas de longitudes desiguales siempre se pueden distinguir entre sí por autómatas con pocos estados.

Historia y límites

El problema de bounding la medida de un autómata que distingue dos cuerdas dadas era primero formuladas por Goralčík y Koubek (1986) & Koubek (1986), quién mostró que la medida de autómata es siempre sublinear. Más tarde, Robson (1989) probó el mejor superior atado sabido, O(n2/5(registro n)3/5), en la medida de autómata que puede ser requerido.[2]​[3]​

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 Robson 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.

Casos especiales

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

  • Si dos palabras binarias tienen diferentes números de ceros o unos, entonces se pueden distinguir entre sí contando su módulo de pesos de Hamming como un primo de tamaño logarítmico, usando 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).
  • Si dos palabras binarias difieren entre sí dentro de su primera o última posición k, 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 solo una fracción polinomialmente pequeña de pares no tiene diferencia en sus posiciones iniciales O (log n).
  • Si dos palabras binarias tienen una distancia d de Hamming, entonces existe una p principal con p = O (d log n) y una posición i en la cual las dos cadenas son diferentes, 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 las posiciones congruentes con i módulo p, es posible distinguir las palabras usando un autómata con estados O (d log n).

Referencias

  1. ↑ Demaine, Erik D.; Eisenstat, Sarah; Shallit, Jeffrey; Wilson, David A. (2011), «Remarks on separating words», Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011, Proceedings, Lecture Notes in Computer Science 6808, Heidelberg: Springer-Verlag, pp. 147-157, MR 2910373, arXiv:1103.4513, doi:10.1007/978-3-642-22600-7_12 ..
  2. ↑ Goralčík, P.; Koubek, V. (1986), «On discerning words by automata», Automata, Languages and Programming: 13th International Colloquium, Rennes, France, July 15–19, 1986, Proceedings, Lecture Notes in Computer Science 226, Berlin: Springer-Verlag, pp. 116-122, MR 864674, doi:10.1007/3-540-16761-7_61 ..
  3. ↑ Robson, J. M. (1989), «Separating strings with small automata», Information Processing Letters 30 (4): 209-214, MR 986823, doi:10.1016/0020-0190(89)90215-9 ..