Jakie znaczące modele automatów mają wielomianowo rozstrzygalne ograniczenie?

Próbuję rozwiązać konkretny problem i pomyślałem, że mogę go rozwiązać za pomocą teorii automatów. Zastanawiam się, jakie modele automatów mają rozstrzygające rozstrzyganie w czasie wielomianowym? tzn. jeśli masz maszyny $M_1, M_2$ , możesz sprawdzić, czy wydajnie.$L(M_1) \subseteq L(M_2)$

Oczywiste, które przychodzą na myśl, to DFA i liczniki ograniczone do odwrócenia, w których liczba liczników jest stała (patrz ten artykuł ).

Jakie inne znaczące klasy można dodać do tej listy?

Im mocniejsze automaty, tym lepiej. Na przykład DFA nie wystarczą, aby rozwiązać mój problem, a liczniki nie mogą tego zrobić z określoną liczbą liczników. (Oczywiście, jeśli staniesz się zbyt potężny, wówczas powstrzymywanie jest albo trudne, jak dla NFA, albo nierozstrzygalne, dla CFG).

Automaty z widocznym przesunięciem w dół (lub automaty z zagnieżdżonymi słowami , jeśli wolisz pracę z zagnieżdżonymi słowami zamiast ze słowami skończonymi), zwiększają ekspresyjną moc deterministycznych automatów skończonych: klasa zwykłych języków jest ściśle zawarta w klasie języków z widocznym przesunięciem. W przypadku deterministycznych, widocznych automatów z przesunięciem w dół, problem włączenia języka można rozwiązać w czasie wielomianowym. Aby uzyskać więcej informacji, zobacz artykuł Alura i Madhusudana, zwłaszcza rozdział 6.

Nawiasem mówiąc, niedeterministyczny wariant widocznych automatów w dół jest wykładniczo bardziej zwięzły niż wariant deterministyczny, ale tam problem z włączeniem języka jest EXPTIME-kompletny, a zatem trudny do rozwiązania.

Alur, R .; Madhusudan, P. (2009). „ Dodawanie struktury zagnieżdżania do słów ”. Dziennik ACM 56 (3): 1–43.

Jeśli w twoim zasięgu znajdują się nieskończone słowa, możesz uogólnić DFA (z warunkiem parzystości) do tak zwanych automatów Good-for-Games (GFG), które nadal zawierają wielomianowe zabezpieczenie.

NFA to GFG, jeśli istnieje strategia , która biorąc pod uwagę dotychczas odczytany prefiks oraz bieżący stan i literę, wybiera przejście, aby przejść do następnego stanu. Strategia σ musi zapewniać, aby dla każdego w w języku automatu przebieg uzyskany przez σ na w był akceptowalny.$\sigma:A^*\times Q\times A\to \Delta$$\sigma$$w$$\sigma$$w$

Ograniczenie dla tych automatów znajduje się w P dla dowolnego warunku stałej parzystości (przez redukcję do gier z parzystością), aw Quasi-P, jeśli indeks parzystości jest częścią danych wejściowych. Mogą być wykładniczo mniejsze niż jakikolwiek równoważny DFA [3].

Jednak na podstawie skończonych słów są to po prostu DFA z możliwymi niepotrzebnymi dodatkowymi przejściami, więc tak naprawdę nie wnoszą nic nowego.

Oto kilka referencji:

[1] Rozwiązywanie gier bez determinacji , Henzinger, Piterman, w CSL 2006

[2] Niedeterminizm w obliczu różnorodnej lub nieznanej przyszłości , Boker, Kuperberg, Kupferman, Skrzypczak, w ICALP 2013

[3] O determinacji automatów Good-for-Games , Kuperberg, Skrzypczak, w ICALP 2015

Non deterministyczny automat XOR (NXA) pasuje do Twojego pytania.

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

NXA są używane do tworzenia małych reprezentacji zwykłych języków, a także niektórych sparametryzowanych algorytmów.

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

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

$M_2$

Pozwól mi naszkicować dowód tego wyniku.

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

Dowód.
Krok 1: Sprowadza się to do uniwersalności jednoznacznych automatów.

$M_1$$M_1$

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

Krok 2: Zdarza się, że jednoznaczne automaty mogą być postrzegane jako automaty NXA (niedeterministyczne automaty XOR w poprzednim poście przez RB) bez oceny, która ma zostać zmieniona (w rzeczywistości rozbieżność między wszystkimi przebiegającymi przebiegami jest równoznaczna z xor nad wszystkimi akceptującymi działa, ponieważ istnieje co najwyżej jedno takie uruchomienie). W przypadku tych automatów uniwersalność jest znana jako wielomian (QED).

$Z/2Z$

[SH85] Richard E. Stearns i Harry B. Hunt III. Na problemach równoważności i ograniczania dla jednoznacznych wyrażeń regularnych, gramatyk regularnych i automatów skończonych. SIAM J. Comput., 14 (3): 598–611, 1985.

[S61] Schützenberger, MP: W sprawie definicji rodziny automatów. Information and Control 4, 245–270 (1961)

Regularne gramatyki LL (k) (tj. Gramatyki, które są zarówno LL (k), jak i regularne ) mogą być konwertowane w czasie wielomianowym na równoważne deterministyczne skończone automaty, a zatem ograniczenie języka i równoważność można rozwiązać w PTIME. Patrz Twierdzenie 4.2 w poniższej pracy (a następnie wyniki dla zastosowania tej obserwacji do schematów programów).

Harry B. Hunt III: Obserwacje złożoności problemów z wyrażaniem regularnym , Journal of Computer and System Sciences 19, 222-236 (1979)