Separar listas de palabras

Hay un problema abierto en los idiomas formales conocido como el Problema de separación; que se indica brevemente como dadas dos cadenas distintas de longitud , qué tan grande de un DFA se requiere para "separarlas", lo que significa aceptar una cadena pero rechazar la otra.$n$

Aquí hay algunos documentos relevantes 1 , 2 . (Tengo algunos más pero no tengo suficiente reputación para publicarlos).

Todos estos discuten el problema de separar dos cadenas distintas. Me pregunto si habido algún trabajo realizado en la zona de separación de listas de cadenas, significado dado dos listas de cadenas, y B , de qué tamaño se requiere DFA para aceptar cada cadena en una y rechazar cada cadena en B . Este problema es equivalente a regex golf.$A$$B$$A$$B$

Hay algunas preguntas básicas en las que he estado trabajando, como si una de las listas es de tamaño o si todas las cadenas son de diferentes longitudes.$1$

He estado buscando pero no he encontrado ningún documento que aborde este tipo de problema. ¿Se ha realizado alguna investigación en esta área?

Gracias por adelantado.

La pregunta que está haciendo se conoce como el problema de separación para los idiomas: dados dos idiomas y L , ¿hay un tercer idioma M (un separador) que los separe, es decir, K ⊆ M y M ∩ L = ∅ .$K$$L$$M$$K \subseteq M$$M \cap L = \emptyset$

Usted está interesado en el caso restringido, donde y L son finitos, y en el tamaño de un DFA para M .$K$$L$$M$

En un artículo de 2013 , los autores indican:

Aunque el problema de separación ocurre con frecuencia, sin embargo, no se ha estudiado sistemáticamente, incluso en el caso restringido, pero aún desafiante, de los idiomas regulares.

Sin embargo, mencionan varios casos especiales que se han resuelto, y que sin duda abarcan el caso finito.

También es posible que desee ver el interpolante de Craig , un problema similar en las fórmulas lógicas. La interpolación se usa, por ejemplo, en la verificación de modelos basada en SAT, en un entorno que creo que está más cerca de lo que está buscando (especialmente con respecto a la finitud de la entrada). Este documento debería ser un buen punto de partida.

$A$$B$

Esto se llama "El problema de las palabras de separación". Las diapositivas de Shallit cubren casi todo lo que se sabe sobre el problema (ver diapositivas1 y diapositivas2 ).