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


9

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:

wprowadź opis zdjęcia tutaj

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.


Jak dokładnie modelujesz „nie przejmuj się”? Wydaje się, że w pewien sposób automaty są niedeterministyczne.
Shaull,

@Shaull Dlaczego miałby to uczynić automat niedeterministycznym. Może się to zdarzyć tylko wtedy, gdy nastąpi kolejne przejście z tego samego stanu, co jest wyraźnie wykluczone.
babou

1
Co to jest a DFA in form of "strip", i.e., no branches? Czy masz jakiś konkretny powód, by sądzić, że można zrobić lepiej niż standardowy algorytm w twoim przypadku?
babou

1
Cześć. Obliczenie rzeczywistego skrzyżowania byłoby świetne, ponieważ uprościłoby wiele rzeczy, ale przydatne byłoby również określenie pustki.
ale64bit

1
właśnie natknąłem się na nowy artykuł na temat wykresów przecięć , czy niektóre z tych teorii mogą być istotne? czy mógłbyś rozwinąć swoją aplikację wspomnianą w komentarzu na Teoretycznym czacie informatyki ? i zaproś innych do kontynuowania dalszej dyskusji.
od

Odpowiedzi:


9

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ępujeNC3)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 jestL-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 iK.=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 klauzulix2)x3)x5, budujesz następujący automat:

gadżet redukcji

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.

2
Wielkie dzięki! Przyjmuję twoją odpowiedź. Pytanie zrodziło się z kilku praktycznych testów, w których wszystko zredukowało się po wielu krokach do skrzyżowania rozwiązań wielu DFA o tej szczególnej charakterystyce. Niemniej jednak zauważyliśmy, że chociaż na końcu uzyskalibyśmy prosty DFA, proces nigdy się nie zakończył, ponieważ pośrednie DFA (podczas sekwencyjnego przecinania się) gwałtownie rosły w wykładniczą liczbę stanów. Zatem pytanie, jak uzyskać odpowiedź bez przechodzenia przez pośrednie „naiwne” kroki.
ale64bit

1
Wielkie dzięki (i przepraszam, że jestem niejasny, jestem poniżej nowicjatu w tej dziedzinie). Teraz jest coś, czego nie rozumiem. Wspominasz, że „w kształcie drzewa” oznacza „unikalną ścieżkę od katalogu głównego do każdego innego węzła”. Ale na przykład na obrazie, który opublikowałeś w edycji, nie byłoby to drzewo (chyba że policzymy przejścia 0/1 jako pojedynczą etykietę)?
ale64bit

1
Masz rację, ale rozumiem, że dopuszczasz przejścia „nie przejmuj się”. Czy tak nie jest?
Michael Blondin,

2
Cześć Michał. Dziękuję za miłą odpowiedź. Mam nadzieję, że wszystko w porządku. :)
Michael Wehar

2
@MichaelWehar Jeśli naprawisz zarówno k i c, wspominasz, że możesz rozwiązać problem „szybko”. Ale nie wspominasz o złożoności czasowej, tylko o złożoności przestrzeni. Co dokładnie „szybko” oznacza w tym kontekście?
ale64bit
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.