Algorytm przecięcia DFA dla szczególnych przypadków

Interesują mnie wydajne algorytmy przecięcia DFA w szczególnych przypadkach. Mianowicie, gdy DFA przecinają się, zachowują określoną strukturę i / lub działają na ograniczonym alfabecie. Czy jest jakieś źródło, w którym mogę znaleźć algorytmy takich przypadków?

Aby pytanie nie było zbyt szerokie, szczególnie interesująca jest następująca struktura: wszystkie przecinające się DFA działają w binarnym alfabecie (0 | 1), mogą także używać symboli „nie przejmuj się”. Co więcej, wszystkie stany mają tylko jedno przejście, z wyjątkiem co najwyżej K stanów specjalnych, które mają tylko dwa przejścia (i te przejścia są zawsze 0 lub 1, ale nie przejmuj się). K jest liczbą całkowitą, mniejszą niż 10 dla celów praktycznych. Mają też jeden stan akceptacji. Dodatkowo wiadomo, że przecięcie to ZAWSZE DFA w formie „paska”, tzn. Bez rozgałęzień, jak na poniższym obrazku:

EDYCJA: Być może opis ograniczenia na wejściowych DFA nie jest bardzo jasny. Spróbuję to poprawić w tym punkcie. Masz jako dane wejściowe T DFA. Każdy z tych DFA działa tylko na alfabecie binarnym. Każdy z nich ma co najwyżej N. stanów. Dla każdego DFA każdy z jego stanów jest jednym z następujących:

1) stan akceptujący (jest tylko jeden i nie można z niego przejść do żadnego innego stanu)

2) stan z dwoma przejściami (0 i 1) do tego samego stanu docelowego (większość stanów jest tego rodzaju)

3) stan z dwoma przejściami (0 i 1) do różnych stanów docelowych (co najwyżej K tego rodzaju)

Gwarantuje się, że istnieje tylko jeden stan akceptacji i że istnieje co najwyżej K stanów typu (3) na każdym wejściowym DFA. Jest także zagwarantowane, że punkt przecięcia DFA wszystkich DFAS wejściowych jest „pasek” (jak opisano powyżej), o rozmiarze mniejszym niż N .

EDYCJA 2: Niektóre dodatkowe ograniczenia, zgodnie z żądaniem DW w komentarzach:

• Wejściowe DFA to DAG.
• Wejściowe DFA są „wyrównane”, zgodnie z definicją DW w komentarzach. Mianowicie, możesz przypisać różne liczby całkowite do każdego stanu w taki sposób, że każde przejście przechodzi od liczby całkowitej u do liczby całkowitej v , tak że u + 1 = v .
• Liczba stanów akceptujących dla każdego wejścia DFA nie przekracza K .

Jakieś pomysły? Dzięki.

Tak , istnieją pewne przypadki problemu wstawienia DFA w pustkę, które znajdują się w P. Moja praca magisterska poświęcona jest temu pytaniu, ale niestety jest w języku francuskim. Jednak większość wyników pojawiła się tutaj w$[2]$.

Gdy alfabet jest jednoargumentowy, wówczas problem jest L-zupełny, gdy każdy DFA ma co najwyżej dwa stany końcowe, a NP-zupełny w przeciwnym razie. Większość innych przypadków to ograniczenia monoidów przejściowych automatów. Na przykład w przypadku aboidowych monoidów przejścia do grupy problem występuje$\text{NC}^3$gdy każdy DFA ma co najwyżej jeden stan końcowy, a NP-zupełny w przeciwnym razie; w przypadku elementarnych monoidów przejściowych z 2 grupami problemem jest$\oplus$L-complete, gdy każdy DFA ma co najwyżej dwa stany końcowe, i NP-complete w przeciwnym razie.

Pozwól mi teraz odpowiedzieć na twoje bardziej precyzyjne pytanie, które można znaleźć tylko w $[1]$. Załóżmy, że masz nadane DFA$\{0,1\}$ i ukształtowane jak drzewa, tzn. istnieje stan $u$ (stan początkowy) taki, że dla każdego stanu $v$ istnieje unikalna ścieżka z $u$ do $v$. Następnie decyzja o braku pustki na skrzyżowaniu to:

1. L-complete dla jednego stanu końcowego w każdym DFA,
2. NL-kompletne dla dwóch stanów końcowych w każdym DFA i
3. NP-complete dla trzech lub więcej stanów końcowych w każdym DFA.

Wyniki twardości nadal obowiązują, nawet jeśli „rozwidlisz” odpowiednio 0, 1 lub 2 razy (to jest twoje $K$). Teraz, jeśli twoje DFA są skierowanymi acyklicznymi wykresami zamiast drzew, to problem jest NP-zupełny nawet z jednym końcowym stanem w każdym DFA i$K=2$; redukcja jest dość prosta i pochodzi z Monotone 1-w-3 3-SAT.

W związku z tym, nie , nie sądzę, że jest skuteczny algorytm dla problemu.

Teraz, jeśli liczba automatów jest stała, możesz porozmawiać z Michaelem Wehar, który niedawno opublikował$[3]$.

EDYCJA: Od kiedy OP zredagował swoje pytanie, wyjaśnię moją odpowiedź jego nowymi wymaganiami. Rozważ problem NP-zupełny Monotone 1-in-3 3-SAT, w którym otrzymujesz formułę w 3-CNF bez negacji, i gdzie musisz ustalić, czy istnieje przypisanie, które sprawia, że dokładnie jedna zmienna jest prawdziwa w każdej klauzuli. Możesz zredukować ten problem do problemu przecięcia się pustki w następujący sposób. Na przykład dla klauzuli$x_2 \lor x_3 \lor x_5$, budujesz następujący automat:

$\hskip2in$

Zauważ, że automaty to drzewa (a zatem DAG), są wypoziomowane i mają trzy stany końcowe. W rzeczywistości trzy stany końcowe mogą zostać połączone w jeden, jeśli jeden jest zadowolony z DAG. Co więcej, tylko dwa stany mają dwa (wyraźne) przejścia wychodzące.

1. Michael Blondin. Complexité raffinée du problème d'intersection d'automates, mgr inż. praca magisterska, Université de Montréal, 2012.
2. Michael Blondin, Andreas Krebs i Pierre McKenzie. Złożoność przecinania automatów skończonych mających niewiele stanów końcowych, złożoność obliczeniowa (CC), 2014.
3. Michael Wehar. Wyniki twardości dla braku pustki na skrzyżowaniu. ICALP, 2014.