Przecięcie DFA w przestrzeni subkwadratowej?

25

Przecięcie dwóch (minimalnych) DFA ze stanami n można obliczyć przy użyciu O (n ² ) czasu i przestrzeni. Jest to ogólnie optymalne, ponieważ otrzymany (minimalny) DFA może mieć n ² stanów. Jeśli jednak wynikowy minimalny DFA ma stany z, gdzie z = O (n), czy można go obliczyć w przestrzeni n ^2-eps , dla pewnej stałej eps> 0? Byłbym zainteresowany takim wynikiem nawet w specjalnym przypadku, w którym wejściowe DFA są acykliczne.

automata-theory dfa Rasmus Pagh
źródło

3

Um ... jeśli dwa DFA w stanie n są acykliczne, to każde z nich akceptuje po prostu skończony zestaw słów o długości co najwyżej n, w którym to przypadku ich przecięcie jest tylko przecięciem dwóch oznaczonych wykresów przejściowych, które będą miały n stanów i można obliczyć w liniowym czasie i przestrzeni. A może coś mi brakuje?

Joshua Grochow

4

Tak, acykliczne DFA akceptują tylko skończony zestaw słów. Ale są przykłady acyklicznych DFA, których przecięcie ma rozmiar n ^ 2. Np. Pomyśl o jednym DFA, który akceptuje łańcuchy postaci AABC (gdzie ABC to łańcuchy długości k), i taki, który akceptuje łańcuchy postaci ABCC.

Rasmus Pagh,

1

Retagging: cs.cc jest oznaczeniem arxiv, więc podane tagi nie potrzebują prefiksu cs.cc.

Suresh Venkat

15

Odpowiedź brzmi „ tak” bez żadnych wymagań co do wielkości automatu. Można go obliczyć w przestrzeni $O(\log^2 n)$ nawet dla $k$ DFA, gdzie $k$ jest stałą.

Niech ( będzie DFA. Pokażemy, że biorąc pod uwagę , obliczania minimal DFA rozpoznawaniem można zrobić w $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$ $i \in [k])$ $k$ $\langle A_1, \ldots, A_k \rangle$ $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ spacja. Najpierw udowadniamy niektóre wyniki techniczne. $O(\log^2 n)$

Definicja 1 : Niech będą dwoma stanami, a następnie iff , $q, r$ $q \equiv r$ $\forall w \in \Sigma^*$ $q . w \in F \Leftrightarrow r . w \in F$

Rozważamy teraz automat podany przez klasyczną konstrukcję kartezjańską. Niech i być stany . $A$ $q = (q_1, \ldots, q_k)$ $r = (r_1, \ldots, r_k)$ $A$

Lemat 1 : Zdecydowanie, czy jest w NL. $q \equiv r$

Dowód (szkic): Pokazujemy, że testowanie nierówności jest w NL i używamy NL = coNL. Odgadnij słowo (jedna litera na raz), takie jak jest stanem końcowym i nie jest. Można to osiągnąć obliczając w przestrzeni dziennika dla i wykorzystując fakt, że jest końcem iff $w \in \Sigma^*$ $q . w$ $r . w$ $q_i . w, r_i . w$ $i \in [k]$ $q$ $q_i \in F_i \, \forall i \in [k]$ $q \not\equiv r$ $w$

Lemat 2 : Decydowanie, czy jest (nie) dostępne, należy do NL. $q$

Dowód (szkic): Zgadnij ( ) ścieżki od do ( ). $z_i$ $q_i$ $i \in [k]$

Definicja 2 : Rozważ stany w porządku leksykograficznym. Zdefiniuj jako pierwszy dostępny stan, a pierwszy dostępny stan po który nie jest równoważny z żadnym poprzednim stanem. Definiujemy jako unikalne takie, że . $A$ $s(1)$ $s(i)$ $s(i-1)$ $c(q)$ $i$ $q \equiv s(i)$

Lemat 3 : można obliczyć w przestrzeni . $s(i)$ $O(\log^2 n)$

Dowód (szkic): Definicja 2 daje algorytm. Używamy liczników do iteracji stanów. Niech i będzie stanem bieżącym. W każdym stanie używamy lematu 2, aby sprawdzić, czy jest dostępne. Jeśli tak, zapętlamy wszystkie poprzednie stany i sprawdzamy, czy którykolwiek z nich jest równoważny . Jeśli nie ma, zwiększamy wartość i wyprowadzamy jeśli . W przeciwnym razie przechowujemy jako i kontynuujemy. Ponieważ przechowujemy tylko stałą liczbę liczników, a nasze testy można przeprowadzić w $k$ $j \leftarrow 0$ $q$ $q$ $q$ $j$ $q$ $j = i$ $q$ $s(j)$ $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$ , to kończy dowód.

Wniosek 1 : można obliczyć w przestrzeni . $c(q)$ $O(\log^2 n)$

Twierdzenie : Minimalizację można przeprowadzić w przestrzeni . $A$ $O(\log^2 n)$

Dowód (szkic): Niechbyć największym takim, że jest zdefiniowane (tj. liczba klas ). Podajemy algorytm wyprowadzający automat gdzie $1 \leq m \leq |Q_0| \cdots |Q_1|$ $i$ $s(i)$ $\equiv$ $A' = (Q', \Sigma, \delta', z', F')$

$Q' = \lbrace s(i) : i \in [m] \rbrace$ ;
$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$ ;
$z' = s(c(q))$ gdzie . $q = (z_0, \ldots, z_k)$

Teraz pokazujemy, jak obliczyć . Dla każdego , oblicz i wypisz przejście . W przypadku lematu 3 i następnej 1 ten algorytm działa w przestrzeni . Można sprawdzić, czy jest minimalne, a . $\delta'$ $i \in [m], a \in \Sigma$ $q \leftarrow s(i) . a$ $\left(s(i), a, s(c(q))\right)$ $O(\log^2 n)$ $A'$ $\text{L}(A') = \text{L}(A)$

Michael Blondin
źródło

3

Niezły algorytm! Oto nieco inny sposób spojrzenia na ten algorytm. Jego rdzeniem jest to, że minimalizację stanu dowolnego DFA można wykonać w czasie wielomianowym i przestrzeni . Następnie łatwo jest zbudować część DFA reprezentującą przecięcie w przestrzeni logarytmicznej (stąd w czasie wielomianowym i przestrzeni ), i możemy skomponować dwie funkcje obliczalne w czasie wielomianowym i spacja (w podobny sposób jak skomponowanie dwóch redukcji przestrzeni logarytmicznej), co daje cały algorytm w czasie wielomianowym i przestrzeni .

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

Tsuyoshi Ito

2

Właśnie widziałem tę odpowiedź ... Nie rozumiem, dlaczego algorytm działa jednocześnie w polytime i . Tak, , ale nie wiadomo, czy - to znaczy, że możemy dostajemy algorytm działający w czasie policy, a możemy uzyskać inny algorytm działający w przestrzeni , ale nie wiem jak rozwiązać problemy w przestrzeni politytime i za pomocą jednego algorytm.

O (\log^{2} n)

$O(\log^2 n)$

N L \subseteq P \cap D S P A C E [\log^{2} n]

$NL \subseteq P \cap DSPACE[\log^2 n]$

N L \subseteq T I S P [n^{O (1)}, \log^{2} n]

$NL \subseteq TISP[n^{O(1)}, \log^2 n]$

O (\log^{2} n)

$O(\log^2 n)$

N L

$NL$

O (\log^{2} n)

$O(\log^2 n)$

Ryan Williams,

Masz rację, ja też nie wiem jak. Napisałem to dawno temu, więc nie jestem pewien, dlaczego napisałem to w ten sposób, ale być może miałem na myśli „czas wielomianowy lub O (log² n)”. Zmienię go, ponieważ wprowadza w błąd. Dziękuję Ci!

Michael Blondin

14

Dick Lipton i koledzy ostatnio pracowali nad tym problemem, a Lipton napisał o nim na blogu:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Wydaje się, że radzenie sobie lepiej niż O (n ^ 2) jest otwarte nawet w bardzo szczególnym przypadku ustalenia, czy przecięcie DFA definiuje pusty język.
W artykule podano konsekwencje złożoności, które wynikałyby ze znacznie ulepszonego algorytmu obsługującego nie tylko 2 DFA na skrzyżowaniu, ale także większe liczby.

Andy Drucker
źródło

1

a co z dolnymi granicami?

Marcos Villagra

1

Żeby wyjaśnić pytania: cieszę się, że spędzam czas O (n ^ 2) (a może nawet czas n ^ O (1)), aby poprawić granicę przestrzeni.

Rasmus Pagh,

13

Jeśli otrzymujesz k DFA (k jest częścią danych wejściowych) i chcesz wiedzieć, czy ich przecięcie jest puste, ten problem jest ogólnie związany z PSPACE:

Dexter Kozen: Lower Bounds for Natural Proof Systems FOCS 1977: 254-266

Być może, jeśli dokładnie przestudiujesz ten dowód (i podobne konstrukcje Liptona i jego współautorów), możesz znaleźć coś w rodzaju dolnej granicy nawet dla ustalonego k.

Ryan Williams
źródło

Dzięki za ten wskaźnik. Zgaduję, że może to prowadzić do n ^ Omega (1) dolnej granicy wymaganej dodatkowej przestrzeni, oprócz danych wejściowych. Ale czy może to prowadzić do dolnej granicy przestrzeni super-liniowej?

Rasmus Pagh,

1

@ user124864 Biorąc pod uwagę DFA z stanami każdy, automat produktu będzie miał stanów. Istnieją dwie sztuczki, które możesz zrobić, aby zmniejszyć jego rozmiar. Pierwszym jest to, że bierzesz pod uwagę osiągalny składnik wykresu produktu. Po drugie, możesz zminimalizować DFA produktu. Pod koniec dnia ustalenie, jaki język jest rozpoznawany przez ten produkt, jest trudne.

k

$k$

n

$n$

n^{k}

$n^k$

Michael Wehar

1

X N L

$XNL$

1

n^{k}

$n^k$

o (1) \cdot k \cdot \log (n)

$o(1) \cdot k \cdot \log(n)$

k^{2} \log^{2} (n)

$k^2 \log^2(n)$

f (k) \cdot \log^{2} (n)

$f(k) \cdot \log^2(n)$

f

$f$

1

n^{k}

$n^k$

n^{k}

$n^k$

7

$A$ $B$ $L(A) \cap L(B)$ $\Theta(|A| \cdot |B|)$ $O(n^2)$ $(q,r)$

$n$ $1 \leq i \leq n$ $i$ $a^i$ $A$ $B$

Michael Blondin
źródło

1

Tak, interesuje mnie automat minimalny lub przynajmniej automat o podobnej wielkości. Dzięki za wskaźniki do jednoargumentowych DFA. Nie wydaje się to jednak bardzo pomocne w przypadku ogólnym.

Rasmus Pagh,

Przecięcie DFA w przestrzeni subkwadratowej?

Odpowiedzi: