Jaka jest złożoność problemu pustki dla dwukierunkowych DFA?

Zastanawiam się, jaka jest złożoność czasowa określania pustki dla dwukierunkowych DFA? Oznacza to, że skończone automaty mogą przesuwać się wstecz na swojej taśmie wejściowej tylko do odczytu.

Według Wikipedii są one równoważne DFA, chociaż równoważny DFA może być wykładniczo większy. Znalazłem złożoność stanu dla ich uzupełnień i skrzyżowań, ale nie dla ich testowania pustki.

Czy ktoś zna gazetę, w której mógłbym to znaleźć?

Przyjaciel Google sugeruje: „ Kompletność PSPACE problemu pustki dla dwustronnych deterministycznych automatów skończonych w ćwiczeniu 5.5.4 wynika z Hunta (1973). ” (Wprowadzenie do teorii obliczeń, Eitan Gurari, Komputer Science Press, 1989, online )

Hunt, H. (1973). „O złożoności czasowej i złożoności języków”, Materiały z 5. dorocznego sympozjum ACM na temat teorii komputerów, 10–19.

( Spojrzałem teraz na odnośnik ) Jak zauważasz, praca została napisana w sposób abstrakcyjny. Kluczową częścią dla nas jest dowód Thm 3.7, w którym sugeruje się, że można zbudować 2FSA który akceptuje prawidłowe obliczenia liniowo ograniczonego automatu M na stałym (!) Ciągu x (który jest zbliżony do definicji PSPACE ). 2FSA A można konstruować w czasie wielomianowym (w rozmiarze M i x ). Obliczenia LBA można zapisać jako x $ x 1 $ … $ x n, gdzie x i są tej samej długości co$\cal A$$\cal M$$x$$\cal A$$\cal M$$x$$x\$x_1\$\dots\$x_n$$x_i$ i są kolejnymi krokami$x$$\cal M$ . Jak check że x I i x i + 1 są równe (do bardzo lokalną zmianę stanu i pojedynczego symbolu jako eksploatacji LBA)? Sprawdzając list po literze, idąc w obie strony na taśmie. Do tego potrzebujemy licznika wielkości | x | realizowane w skończonej kontroli państwowej A .$\cal A$$x_i$$x_{i+1}$$|x|$$\cal A$

Okazuje się, że problem jest wspomniany w załączniku do klasycznej literatury Garey & Johnson, Computers and Intractability , problem [AL2] „Dwukierunkowa automatyczność stanu skończonego” z wyraźną uwagą „PSPACE-complete, nawet jeśli jest deterministyczny ”. Ponownie odnieś się do Hunt, z wyjaśnieniem „Transformacja z liniowego ograniczenia automatycznego przyjęcia” (Biorąc pod uwagę LBA A i wejście x , czy A przyjmuje x ?). Ten ostatni problem dotyczy [AL3] w odniesieniu do słynnego artykułu Karpa (1972) „Reducibility Among Combinatorial Problems” (gdzie akceptacja LBA jest wymieniona jako rozpoznawanie wrażliwe na kontekst).$\cal A$$\cal A$$x$$\cal A$$x$

Brak pustki na skrzyżowaniu dla DFA jest następujący:

Dane wejściowe: skończona lista DFA , D 2 , ..., D k .$D_1$$D_2$$D_k$

Pytanie: Czy istnieje ciąg taki, że dla każdego$w$ , D i akceptuje w ? Innymi słowy, czy przecięcie powiązanych z nimi zwykłych języków nie jest puste?$i \in [k]$$D_i$$w$

Skrzyżowanie Brak pustki jest klasycznym problemem kompletnym dla PSPACE (Kozen 1977 - „Dolne granice dla systemów proofów naturalnych”)

Trafność: Istnieje przyjemna i prosta sparametryzowana redukcja z braku pustki na skrzyżowaniu dla jednokierunkowych DFA do braku pustki dla dwukierunkowych DFA.

Wybierz liczbę DFA jako parametr dla braku pustki na skrzyżowaniu i liczbę zwojów (przełączanie z ruchu w lewo na prawo lub z prawej na lewą) jako parametr dla braku pustki dla dwukierunkowych DFA.

Roszczenie:$k$$(2k-2)$

Biorąc pod uwagę DFA , D 2 , ...,$D_1$$D_2$$D_k$$(2k-2)$

$D_1$$D_2$$D_3$$D_k$

Jeśli wszyscy zaakceptują, wówczas dokonuje oceny wszystkich, a następnie akceptuje. Jeśli jeden z nich odrzuci, to przestaje (nie kończy oceny wszystkich) i natychmiast odrzuca.

$k$$n^k$

Powiązany link: /cstheory/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time/29166#29166

$(2k-2)$$n^k$

Wniosek: jeśli miałbyś znaleźć szybszy algorytm nieopróżnienia dla dwukierunkowych DFA, to prowadziłoby to do wydajniejszej symulacji maszyn niedeterministycznych. Daj mi znać, jeśli masz jakieś uwagi. Dziękujemy za pytanie! :)