El costo de una consulta de equivalencia para DFA

12

Inspirado por esta pregunta , tengo curiosidad por lo siguiente:

¿Cuál es la complejidad del peor caso de verificar si un DFA determinado acepta el mismo lenguaje que una expresión regular dada?

¿Se sabe esto? La esperanza sería que este problema esté en P, que exista un algoritmo polinomial del tamaño de ambos.

automata-theory lg.learning regular-expressions dfa Lev Reyzin
fuente

Respuestas:

16

De acuerdo con Garey y Johnson (p. 174), LA EXPRESIÓN REGULAR NO UNIVERSALIDAD está completa en PSPACE. Este es el problema de decidir si una expresión regular más de no no generar todas las cadenas. Entonces su problema también es PSPACE-complete.{0,1}

ArBrCBCCDACL(A)=L(r)D2poly(n)L(D)=∅NSPACE(poly(n))=NPSPACE=PSPACE, la última igualdad debido al teorema de Savitch.

Yuval Filmus
fuente
¿Estás seguro de que está en PSPACE (si no, solo sería PSPACE-HARD)? ¿O tal vez es suficiente verificar todas las cadenas de alguna longitud polinómica para ver si la expresión regular y el DFA están de acuerdo en todas ellas? ¿Eso es obvio? :-)
Neal Young
44
Recuerde que la accesibilidad está en NL, por lo tanto, aunque el DFA correspondiente a la expresión regular es exponencial, dado que el acceso al oráculo es barato, podemos determinar si la diferencia simétrica está vacía o no en NPSPACE = PSPACE.
Yuval Filmus
No veo el resultado de la dureza. Es decir, ¿cómo reduce el problema anterior a la universalidad de las expresiones regulares?
Markus
2
Elija el DFA que acepte todo. Para mostrar dureza, reduce la EXPRESIÓN REGULAR NO UNIVERSALIDAD al problema en cuestión.
Yuval Filmus
1
@YuvalFilmus ¡Gracias por la referencia! Probablemente deberías agregar tu primer comentario a tu respuesta para completar, en ambos sentidos de la palabra :)
Lev Reyzin