minimizando el tamaño de la expresión regular para conjuntos finitos

15

Se sabe que minimizar el tamaño de una expresión regular es completo para PSPACE, incluso si tenemos un DFA como la especificación del lenguaje .

¿Cuáles son los resultados si el idioma es finito?

Uno puede considerar este problema en dos modelos:

  1. La entrada es todas las cadenas en el idioma, y ​​medimos el tamaño de entrada por la suma de la longitud de todas las cadenas.
  2. La entrada es un DFA y medimos el tamaño de entrada por el número de estados del DFA.

La estrella de Kleene no es útil en el caso finito, así que solo , | y (concatenación) se usan en la expresión. Por supuesto, la longitud de una expresión regular parece arbitraria. En cambio, uno puede dar peso a cada operación (incluye agregar paréntesis) y pedir minimizar el peso de la expresión regular.()El |

Editar: como notó adrianN, está relacionado con códigos gramaticales. NP-complete produce la gramática libre de contexto de longitud mínima para describir un conjunto finito. No está claro por qué la gramática libre de contexto de tamaño mínimo puede implicar mucho sobre la expresión regular de tamaño mínimo. Tal vez una regla de reescritura inteligente pueda relacionar estos dos, y demostrar que en el primer modelo, el problema está en NP.

Chao Xu
fuente
3
Esto parece estar relacionado con los códigos gramaticales .
adrianN
supongamos que el tamaño de entrada es limitado. entonces kleene star podría ser válida. Por lo tanto, tiene sentido definir si el tamaño de entrada está (naturalmente) limitado a la cadena más larga en el lenguaje finito. & también si kleene star aún está excluida en ese caso. también, como una heurística (¿obvia?), minimizar una DFA y construir un RE a partir de eso es una estrategia ... también tenga en cuenta que los RE (con sustitución variable) tienen una estructura tipo DAG y no se conocen muchos thms (fuertes) sobre la minimización de las estructuras tipo DAG ... Los RE sin sustitución de variables son como líneas (fórmulas) y pueden ser más fáciles de trabajar con ...
vzn
otro ángulo Se sabe que los "derivados" de RE introducidos por brzozowski son útiles para convertir RE directamente en DFA; véase, por ejemplo , derivados de expresión regular reexaminados por Owens, Reppy, Turon. tal vez haya alguna forma de usar la misma estructura para el problema inverso. de todos modos, aunque en general parece ser un problema abierto ...
vzn

Respuestas:

4

Σ2PAGk

Creo que no se conocen más resultados con respecto a sus problemas. Para un problema de optimización de aspecto similar, donde el objetivo es encontrar un autómata finito no determinista equivalente mínimo en lugar de una expresión regular, se conocen los siguientes resultados:

  • rePAGrePAG
  • nortePAG
  • L{0 0,1}metronortePAG

Cuidado: a diferencia de la configuración de idiomas infinitos, no veo una reducción directa del caso de minimización de NFA a los problemas de su pregunta.

Referencias

(1) Hermann Gruber y Markus Holzer. Complejidad computacional de la minimización de NFA para lenguajes finitos y unarios . En: Primera Conferencia Internacional sobre Teoría y Aplicaciones de Lenguajes y Autómatas (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber y Markus Holzer. Inaproximabilidad del estado no determinista y la complejidad de la transición, suponiendo P <> NP . En: 11ª Conferencia Internacional sobre Desarrollos en Teoría del Lenguaje (DLT 2007), LNCS 4588, pp. 205-216, 2007.

L={w}w

Hermann Gruber
fuente
-6

aparentemente sin una respuesta conocida exacta o mejor que esta, aquí hay una referencia cercana / reciente a la investigación específicamente sobre el tema de minimizar las ER (que es un ángulo aparentemente poco común):

Minimizando las NFA y las expresiones regulares (2005) por Gregor Gramlich, Georg Schnitger

Mostramos resultados de inaplicabilidad con respecto a la minimización de autómatas finitos no deterministas (nfa), así como expresiones regulares relativas a los nfa dados, expresiones regulares o autómatas finitos deterministas (dfa). Mostramos que es imposible minimizar eficientemente una nfa dada o una expresión regular con n estados, transiciones, resp. símbolos dentro del factor o (n), a menos que P = PSPACE. Nuestros resultados de inaplicabilidad para un determinado dfa con n estados se basan en suposiciones criptográficas y mostramos que cualquier algoritmo eficiente tendrá un factor de aproximación de al menos poli (log n). Nuestra configuración también nos permite analizar el problema mínimo constante de dfa.

vzn
fuente
44
Esta pregunta se hizo específicamente porque este documento no aborda lo que sucede cuando el idioma es finito.
Chao Xu
1
bien, entonces sirve como [relevante / nec] bkg. pero tenga en cuenta que si la otra pregunta no tiene una respuesta [publicada], ciertamente tampoco es sorprendente que esta tampoco, un ángulo de variación cercana podría no ayudar mucho. también [ mea culpa ] no notó que el documento fue citado por MdB en la otra pregunta.
vzn