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

18

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)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).

jmite
źródło
czy jesteś zainteresowany nieskończonymi słowami, czy konkretnie słowami skończonymi?
Denis
2
Nie jestem pewien, czy nieokreślone słowa odnoszą się do mojego konkretnego problemu, ale z pewnością są w zakresie pytania!
jmite

Odpowiedzi:

15

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.

Hermann Gruber
źródło
1
Punkty bonusowe za znalezienie modelu mocniejszego niż zwykłe języki! Słyszałem o nich, ale nie wiedziałem, że dla deterministycznej wersji rzeczy są wielomianowe!
jmite
Wielkie dzięki. Jeśli możesz skorzystać z tego modelu, daj nam znać w tym miejscu.
Hermann Gruber
13

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.σ:ZA×Q×ZAΔσwσ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

Denis
źródło
Czy zatem GFG mogą być mniejsze niż równoważny DFA dla nieskończonego wejścia? tj. czy jest jakiś wzrost wydajności dla skończonego wkładu?
jmite
2
jest już napisane w odpowiedzi, każda GFG na skończonych słowach jest w rzeczywistości DFA z dodatkowymi bezużytecznymi przejściami, więc nie ma przyrostu wydajności dla skończonych słów.
Denis
Okej, po prostu nie byłam pewna, czy interpretuję to dobrze. Dzięki!
jmite
11

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

M.wΣ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)L.(M.2))

RB
źródło
7

M.1M.2)L.(M.2))L.(M.1)

M.2)

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


M.1M.2)M.2)L.(M.1)L.(M.2))

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

M.1M.1

L.(M.1)L.(M.2))L.(M.2))L.(M.1)do

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/2)Z


[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)

Thomas Colcombet
źródło
1

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)

Hermann Gruber
źródło