Quels modèles d'automates notables ont un confinement polynomialement décidable?

J'essaie de résoudre un problème particulier et j'ai pensé que je pourrais le résoudre en utilisant la théorie des automates. Je me demande, quels modèles d'automates ont un confinement décidable en temps polynomial? c'est-à-dire que si vous avez des machines vous pouvez tester si efficacement.$M_1, M_2$$L(M_1) \subseteq L(M_2)$

Les plus évidents qui me viennent à l'esprit sont les DFA et les machines de comptage à bornes inversées où le nombre de compteurs est fixe (voir cet article ).

Quelles autres classes notables peuvent être ajoutées à cette liste?

Plus les automates sont puissants, mieux c'est. Par exemple, les DFA ne suffisent pas à résoudre mon problème et les machines de comptage ne peuvent pas le faire avec un nombre fixe de compteurs. (Naturellement, si vous devenez trop puissant, le confinement est soit insoluble, comme pour les NFA, ou indécidable, pour les CFG).

Les automates visiblement pushdown (ou automates imbriqués de mots , si vous préférez travailler avec des mots imbriqués au lieu de mots finis) étendent la puissance expressive des automates finis déterministes: la classe des langages réguliers est strictement contenue dans la classe des langages visiblement pushdown. Pour les automates déterministes visiblement pushdown, le problème d'inclusion de langage peut être résolu en temps polynomial. Pour plus de détails, voir l'article d'Alur et Madhusudan, en particulier le chapitre 6.

Soit dit en passant, la variante non déterministe des automates visiblement pushdown est exponentiellement plus succincte que la variante déterministe, mais là, le problème d'inclusion du langage est EXPTIME-complet et donc insoluble.

Alur, R .; Madhusudan, P. (2009). " Ajout d'une structure d'imbrication aux mots ". Journal de l'ACM 56 (3): 1–43.

Si des mots infinis sont dans votre portée, vous pouvez généraliser DFA (avec condition de parité) aux soi-disant automates Good-for-Games (GFG), qui ont toujours un confinement polynomial.

Un NFA est GFG s'il existe une stratégie , qui, étant donné le préfixe lu jusqu'à présent et l'état et la lettre actuels, choisit une transition pour passer à l'état suivant. La stratégie doit garantir que pour chaque dans la langue de l'automate, l'exécution donnée par sur est acceptée.σ w σ $\sigma:A^*\times Q\times A\to \Delta$$\sigma$$w$$\sigma$$w$

Le confinement de ces automates est en P pour toute condition de parité fixe (en réduisant aux jeux de parité), et en Quasi-P si l'index de parité fait partie de l'entrée. Ils peuvent être exponentiellement plus petits que tout DFA équivalent [3].

Cependant, sur les mots finis, ce ne sont que des DFA avec des transitions supplémentaires inutiles possibles, donc ils n'apportent vraiment rien de nouveau.

Voici quelques références:

[1] Résolution de jeux sans déterminisation , Henzinger, Piterman, dans CSL 2006

[2] Non-déterminisme en présence d'un avenir divers ou inconnu , Boker, Kuperberg, Kupferman, Skrzypczak, dans ICALP 2013

[3] Sur la détermination des automates bons pour les jeux , Kuperberg, Skrzypczak, dans ICALP 2015

Un automate XOR non déterministe (NXA) répond à votre question.

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

Les NXA sont utilisés pour créer de petites représentations de langages réguliers ainsi que certains algorithmes paramétrés.

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

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

$M_2$

Permettez-moi d'esquisser une preuve de ce résultat.

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

Preuve.
Étape 1: Cela se réduit à l'universalité des automates sans ambiguïté.

$M_1$$M_1$

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

Étape 2: Il arrive que les automates sans ambiguïté puissent être considérés comme des automates NXA (automates XOR non déterministes dans le post précédent par RB) sans évaluation à modifier (en effet, une disjonction sur toutes les exécutions acceptées équivaut à un xor sur toutes les acceptations s'exécute, car il n'y en a pas plus). Pour ces automates, l'universalité est connue pour être polynomiale (QED).

$Z/2Z$

[SH85] Richard E. Stearns et Harry B. Hunt III. Sur les problèmes d'équivalence et de confinement pour les expressions régulières non ambiguës, les grammaires régulières et les automates finis. SIAM J. Comput., 14 (3): 598–611, 1985.

[S61] Schützenberger, député: sur la définition d'une famille d'automates. Information and Control 4, 245-270 (1961)

Les grammaires LL (k) régulières (c'est-à-dire les grammaires à la fois LL (k) et régulières ) peuvent être converties en temps polynomial en automates déterministes finis équivalents, et ainsi le confinement et l'équivalence du langage peuvent être résolus dans PTIME. Voir le théorème 4.2 dans l'article suivant (et les résultats par la suite pour une application de cette observation aux programmes).

Harry B. Hunt III: Observations on the Complexity of Regular Expression Problems , Journal of Computer and System Sciences 19, 222-236 (1979)