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