Gibt es eine genau definierte Divisionsoperation für endliche Automaten?

15

Hintergrund:

Bei zwei deterministischen endlichen Automaten A und B bilden wir das Produkt C, indem wir die Zustände in C das kartesische Produkt von Zuständen in A und Zuständen in B sein lassen C ist der Schnittpunkt der Sprachen für A und B.

Fragen:

(1) Können wir C durch B "teilen", um A zu finden? Ist A einmalig bis zum Isomorphismus? Wir kümmern uns um die Zustandsdiagramme, nicht um die Sprachen hier und unten. Daher dürfen die Zustandsdiagramme nicht komprimiert werden, um die Anzahl der Zustände zu verringern.

(2) Wenn A eindeutig ist, gibt es einen effizienten Algorithmus, um es zu finden?

(3) Hat jeder deterministische endliche Automat eine eindeutige Faktorisierung in "Primzahlen"? Eine Primzahl bedeutet hier einen Automaten, der nicht berücksichtigt werden kann, dh als Produkt von 2 kleineren Automaten geschrieben ist.

  • Arbeite mit @MichaelWehar
Wer bist du?
quelle
5
Die klassische Zerlegung ist die Krohn-Rhodes-Theorie - viel zu sehen.
2
Betrachten wir Brzozowski-Derivate. en.wikipedia.org/wiki/Brzozowski_derivative
Vijay D
2
@halfTrucker Krohn-Rhodes-Theorie befasst sich mit Kranzprodukt. Das OP fragt nach kartesischem Produkt.
Scaaahu
2
Danke @halfTrucker, das ist wirklich interessant! Wie Scaaahu sagt, suche ich kartesisches Produkt, aber Ihre Referenz ist immer noch großartig.
Whosyourjay

Antworten:

8

Schauen Sie sich dieses MFCS 2013-Papier an , das die Komposition in Automaten untersucht. Vielleicht hilft es.

Shaull
quelle
2
+1 für den Link. Aus der Diskussion des Artikels zitiert: Während der allgemeine Fall noch offen ist , scheint es, dass der Artikel nur den Fall von Permutationsautomaten untersucht. Gibt es neuere Entwicklungen für allgemeine Fälle? Ich meine im Sinne von kartesischem Produkt? (Krohn-Rhodes-Theorie befasst sich mit Kranzprodukt) Danke.
Scaaahu
3
Ich kenne keine neuen Entwicklungen. Ich kann Ihnen sagen, dass es keine direkten Folgemaßnahmen zu diesem Papier gab. Dies kann jedoch als Hinweis darauf dienen, dass das Problem in der Tat nicht einfach ist.
Shaull
4

Geben wir einen offensichtlichen Weg, um einen "Faktor" des Produktautomaten wiederzugewinnen. Wenn und A = A 1 × A 2 den Produktautomaten bezeichnet, dann definieren wir π 1 ( ( q , q ) ) : = q dh A 2 einfach vergessenAi=(Qi,δi,q0i,Fi),i=1,2A=A1×A2

π1((q,q)): =q
EIN2oder auf die zweite Komponente projiziert, haben wir , auch wenn wir δ 1 ( q , x ) kennen wollen, wählen Sie einige q Q 2 und berechnen Sie im Produktautomaten π ( ( δ 1 ( q , x ) , δ 2 ( q ' , x ) ) = δ 1 ( qQ.1=π(Q.1×Q.2)δ1(q,x)qQ2 , daher können wir auch den Übergang in A 1 wiederherstellen.π((δ1(q,x),δ2(q,x))=δ1(q,x)A1

Wenn wir also wissen, dass ein Automat ein kartesischer (oder externer) Produktautomat ist, können wir die Faktoren leicht wiederfinden.

Aber ich denke, das ist nicht das, was Sie in Bezug auf Ihre anderen Fragen im Sinn haben. Hier stellen sich zwei Fragen (im Folgenden meine ich mit Automatenisomorphismus isomorph als Zustandsgraph, dh ohne Berücksichtigung von Anfangs- oder Endzuständen, wie Sie sagten, die Sprache ist hier nicht so sehr von Belang):

1) Ist diese Zerlegung bei jedem Automaten, der zu einem Produktautomaten isomorph ist (dh auf irgendeine Weise zerlegt werden könnte), einer endlichen Anzahl von Automaten im wesentlichen einzigartig? (vorausgesetzt, die Faktoren könnten nicht weiter zerlegt werden, sonst offensichtlich nicht). Genauer gesagt, wenn für nicht zusammensetzbare Automaten A i , B j

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

2) Bei zwei beliebigen Automaten A,BCA=B×C

Es ist leicht, die notwendigen Bedingungen dafür abzuleiten, aber ich sehe keine einfachen ausreichenden Kriterien dafür, dass ein Automat ein Faktor eines anderen ist.

π1((δ1(q,x),δ2(q,x))=δ1(q,x)=δ1(π1(q,q),x)
qQ1,qQ2πEIN1×EIN2EIN2

EIN BBEIN

BEIN

MNMN

H. Straubing, P. Weil Einführung in endliche Automaten und deren Verknüpfung mit der Logik,

Kurswebsite mit vielen Informationen.

Bemerkung : Es gibt auch einen anderen Begriff von " Quotientierung ", siehe Wikipedia: Quotientautomat , aber dies ist nur eine Regel für das Zusammenfallen von Zuständen und wird in Lern- / Sprachinferenzalgorithmen oder bei der Zustandsminimierung verwendet.

StefanH
quelle