Czy istnieje dobrze określona operacja podziału automatów skończonych?

15

Tło:

Biorąc pod uwagę dwa deterministyczne automaty skończone A i B, tworzymy iloczyn C, pozwalając, by stany w C były iloczynem kartezjańskim stanów w A i stanów w B. Następnie wybieramy stany przejściowe, początkowe i końcowe, aby język został zaakceptowany przez C to przecięcie języków dla A i B.

Pytania:

(1) Czy możemy „podzielić” C przez B, aby znaleźć A? Czy jest nawet wyjątkowy, aż do izomorfizmu? Dbamy o diagramy stanu, a nie o języki tutaj i poniżej. Dlatego nie zezwalamy na kompresowanie diagramów stanów w celu zmniejszenia liczby stanów.

(2) Jeśli A jest unikalny, czy istnieje skuteczny algorytm do jego znalezienia?

(3) Czy każdy deterministyczny automat skończony ma unikalną faktoryzację na „liczby pierwsze”. Liczba pierwsza oznacza tutaj automat, którego nie można rozłożyć na fakt, to znaczy napisany jako produkt 2 mniejszych automatów.

  • Pracuj z @MichaelWehar
Whosyourjay
źródło
5
Klasycznym rozkładem jest teoria Krohna-Rhodesa - wiele do zobaczenia.
2
Rozważ pochodne Brzozowskiego. en.wikipedia.org/wiki/Brzozowski_derivative
Vijay D
2
@halfTrucker Teoria Krohna-Rhodesa dotyczy produktu wieńcowego. OP pyta o produkt kartezjański.
scaaahu
2
Dzięki @halfTrucker, to jest naprawdę interesujące! Jak mówi scaaahu, szukam produktu kartezjańskiego, ale twoje referencje są nadal świetne.
Whosyourjay,

Odpowiedzi:

8

Spójrz na ten artykuł MFCS 2013 , który bada kompozycję w automatach. Być może to pomoże.

Shaull
źródło
2
+1 za link. Cytując z dyskusji na temat artykułu, Podczas gdy ogólny przypadek jest nadal otwarty , wydaje się, że artykuł bada tylko przypadek automatu permutacji. Czy pojawiły się jakieś nowsze opracowania dotyczące ogólnych przypadków? Mam na myśli w sensie produktu kartezjańskiego? (Teoria Krohna-Rhodesa dotyczy produktu wieńcowego) Dzięki.
scaaahu
3
Nie znam żadnych ostatnich wydarzeń. Mogę powiedzieć, że nie było bezpośrednich działań następczych w związku z tym dokumentem. Może to jednak wskazywać, że problem nie jest wcale łatwy.
Shaull,
4

Podajmy oczywisty sposób na odzyskanie jednego „czynnika” automatu produktu. Jeśli i A = A 1 × A 2 oznacza automat produktu, to jeśli zdefiniujemy π 1 ( ( q , q ) ) : = Q czyli tylko zapomina o A 2Ai=(Qi,δi,q0i,Fi),i=1,2A=A1×A2

π1((q,q)):=q
A2lub rzutując na drugi komponent, mamy , także jeśli chcemy wiedzieć δ 1 ( q , x ) wybierz trochę q Q 2 i oblicz w automacie iloczynu π ( ( δ 1 ( q , x ) , δ 2 ( q , x ) ) = δ 1 ( qQ1=π(Q1×Q2)δ1(q,x)qQ2 , a więc, że może także odzyskiwać przejścia w A 1 .π((δ1(q,x),δ2(q,x))=δ1(q,x)A1

Więc jeśli wiemy, że automat jest kartezjańskim (lub zewnętrznym) automatem produktu, możemy łatwo odzyskać czynniki.

Ale myślę, że nie to masz na myśli w odniesieniu do innych pytań. Pojawiają się tutaj dwa pytania (dalej przez automatyczny izomorfizm mam na myśli izomorficzny jako graf stanu, tj. Bez względu na stany początkowe lub końcowe, jak powiedziałeś, język nie jest tutaj tak bardzo istotny):

A1××AkB1××Bl
Ai,Bjk=lAiBπ(i)π:{1,k}{1,k}

A,BCA=B×C

Łatwo jest ustalić niezbędne warunki, ale nie widzę żadnych łatwych wystarczających kryteriów, aby jakiś automat był czynnikiem innym.

π1((δ1(q,x),δ2(q,x))=δ1(q,x)=δ1(π1(q,q),x)
qQ1,qQ2πA1×A2A2

A BBA

BA

MNMN

H. Straubing, P. Weil Wprowadzenie do automatów skończonych i ich związek z logiką,

Strona internetowa kursu z dużą ilością informacji.

Uwaga : Istnieje również inne pojęcie „ ilorazu ”, patrz wikipedia: iloraz automat , ale jest to tylko reguła dla stanów zwijania i stosowana w algorytmach uczenia się / wnioskowania języka lub minimalizacji stanu.

StefanH
źródło