complexity-classes – Problema de contención de un NFA acíclico en un NFA

Pregunta:

Sean $ A $ y $ B $ NFA, de modo que $ A $ sea ​​acíclico.

En el caso general, decidir si $ L (A) \ subseteq L (B) $ es $ PSPACE $ -difícil. Sin embargo, dado que $ A $ es acíclico, sabemos que por cada $ w \ en L (A) $ , se mantiene que $ | w | $ es lineal en $ | A | $ . De ello se deduce que si $ L (A) \ nsubseteq L (B) $ , debe haber un testigo polinomial $ w \ en L (A) \ setminus L (B) $ . Por tanto, el problema de contención cuando $ A $ es acíclico está en $ coNP $ .

¿Se puede demostrar que es $ coNP $ -hard?

Respuesta:

Esto es difícil incluso si $ B $ también es acíclico.

Sea $ D = \ bigvee_ {i = 1} ^ m T_i $ un DNF en las variables $ x_1, \ dots, x_n $ . Podemos construir fácilmente un NFA $ B $ aceptando exactamente la asignación satisfactoria de $ D $ , es decir, las palabras $ w \ in \ {0,1 \} ^ n $ tales que la asignación $ a $ definida como $ a ( x_i) = w_i $ satisface $ D $ .

Para hacer esto, construye un autómata $ B_i $ con $ n + 2 $ estados que reconocen $ T_i $ y agrega un estado inicial que elige $ i $ de forma no determinista y salta a $ B_i $ con una transición $ \ epsilon $ .

$ B_i $ tiene los estados $ q_1, \ dots, q_ {n + 1} $ y $ rechazar $ . El estado inicial es $ q_1 $ . Cuando está en el estado $ q_j $ por $ j \ leq n $ : si $ x_j $ no aparece en $ T_i $ , entonces entra en el estado $ q_ {j + 1} $ por cada valor de la siguiente letra. Si $ x_j $ aparece positivamente en $ T_i $ , entonces ingresa $ q_ {j + 1} $ solo si lee la letra $ 1 $ . Si lee la letra $ 0 $ , ingresa en el estado $ rechazar $ . Si $ x_j $ aparece negativamente en $ T_i $ , haga lo mismo intercambiando $ 0 $ y $ 1 $ . $ q_ {n + 1} $ es el único estado final.

Ahora construye $ A $ , acíclico, que acepta cada palabra de longitud $ n $ (la misma construcción que antes para $ T_i $ vacío).

Está claro que $ L (A) \ subseteq L (B) $ iff $ D $ es una tautología, que es coNP-completa.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım