¿Qué modelos notables de autómatas tienen una contención polinomialmente decidible?

Estoy tratando de resolver un problema en particular, y pensé que podría resolverlo usando la teoría de autómatas. Me pregunto, ¿qué modelos de autómatas tienen una contención decidible en tiempo polinómico? es decir, si tiene máquinas , puede probar si eficiente. L ( M 1 ) ⊆ L ( M 2$M_1, M_2$$L(M_1) \subseteq L(M_2)$

Los obvios que vienen a la mente son los DFA y las máquinas de contadores con límite de inversión donde se fija el número de contadores (consulte este documento ).

¿Qué otras clases notables se pueden agregar a esta lista?

Cuanto más poderoso sea el autómata, mejor. Por ejemplo, los DFA no son suficientes para resolver mi problema, y ​​las máquinas de mostrador no pueden hacerlo con un número fijo de contadores. (Naturalmente, si te vuelves demasiado poderoso, entonces la contención es intractible, como para NFA, o indecidible, para CFG).

Automatismos visiblemente pushdown (o autómatas de palabras anidadas , si prefiere trabajar con palabras anidadas en lugar de palabras finitas) extienda el poder expresivo de los autómatas finitos deterministas: la clase de lenguajes regulares está estrictamente contenida dentro de la clase de lenguajes visiblemente pushdown. Para los autómatas deterministas de pushdown visible, el problema de inclusión del lenguaje se puede resolver en tiempo polinómico. Para más detalles, vea el documento de Alur y Madhusudan, especialmente el Capítulo 6.

Por cierto, la variante no determinista de los autómatas visiblemente pushdown es exponencialmente más sucinta que la variante determinista, pero el problema de inclusión del lenguaje es EXPTIME-complete y, por lo tanto, intratable.

Alur, R .; Madhusudan, P. (2009). " Agregar estructura de anidamiento a las palabras ". Revista de la ACM 56 (3): 1–43.

Si hay infinitas palabras dentro de su alcance, puede generalizar DFA (con condición de paridad) a los llamados autómatas Good-for-Games (GFG), que todavía tienen contención polinómica.

Un NFA es GFG si hay una estrategia , que dado el prefijo leído hasta ahora y el estado y la letra actuales, elige una transición para pasar al siguiente estado. La estrategia debe garantizar que por cada en el lenguaje del autómata, la ejecución producida por en acepte.σ w σ $\sigma:A^*\times Q\times A\to \Delta$$\sigma$$w$$\sigma$$w$

La contención para estos autómatas está en P para cualquier condición de paridad fija (reduciéndola a juegos de paridad), y en Cuasi-P si el índice de paridad es parte de la entrada. Pueden ser exponencialmente más pequeños que cualquier DFA equivalente [3].

Sin embargo, en palabras finitas, son solo DFA con posibles transiciones adicionales inútiles, por lo que realmente no aportan nada nuevo.

Aquí hay algunas referencias:

[1] Resolviendo juegos sin determinación , Henzinger, Piterman, en CSL 2006

[2] No determinismo en presencia de un futuro diverso o desconocido , Boker, Kuperberg, Kupferman, Skrzypczak, en ICALP 2013

[3] Sobre la determinación de autómatas buenos para juegos , Kuperberg, Skrzypczak, en ICALP 2015

Un autómata XOR no determinista (NXA) se ajusta a su pregunta.

$M$$w\in \Sigma^*$$L(M)$

Los NXA se utilizan para crear pequeñas representaciones de lenguajes regulares, así como algunos algoritmos parametrizados.

$O(|Q|^3$$L(M_1)\subseteq L(M_2)$

$M_1$$M_2$$L(M_2)$$L(M_1)$

$M_2$

Déjame esbozar una prueba de este resultado.

$M_1$$M_2$$M_2$$L(M_1)\subseteq L(M_2)$

Prueba.
Paso 1: Esto se reduce a la universalidad de autómatas inequívocos.

$M_1$$M_1$

$L(M_1)\subseteq L(M_2)$$L(M_2)\cup L(M_1)^c$

Paso 2: Sucede que los autómatas inequívocos pueden verse como autómatas NXA (autómatas XOR no deterministas en la publicación anterior de RB) sin que haya que cambiar la evaluación (de hecho, una disyunción sobre todas las ejecuciones de aceptación es equivalente a una xor sobre la aceptación general corre ya que hay como máximo una de esas carreras). Para estos autómatas, se sabe que la universalidad es polinómica (QED).

$Z/2Z$

[SH85] Richard E. Stearns y Harry B. Hunt III. Sobre los problemas de equivalencia y contención para expresiones regulares inequívocas, gramáticas regulares y autómatas finitos. SIAM J. Comput., 14 (3): 598-611, 1985.

[S61] Schützenberger, MP: Sobre la definición de una familia de autómatas. Información y control 4, 245–270 (1961)

Las gramáticas LL (k) regulares (es decir, las gramáticas que son LL (k) y regulares ) se pueden convertir en tiempo polinomial en autómatas finitos deterministas equivalentes y, por lo tanto, la contención y equivalencia del lenguaje se pueden resolver en PTIME. Consulte el Teorema 4.2 en el siguiente documento (y los resultados posteriores para una aplicación de esta observación a los esquemas de programas).

Harry B. Hunt III: Observaciones sobre la complejidad de los problemas de expresión regular , Journal of Computer and System Sciences 19, 222-236 (1979)