Die Anzahl der Zustände lokaler Automaten

10

Ein deterministischer Automat heißt k- lokal für k > 0, wenn für jedes w X k die Menge { δ ( q , w ) : q Q } höchstens enthält ein Element. Intuitiv bedeutet dies, dass wenn ein Wort w der Länge k zu einem Zustand führt, dieser Zustand eindeutig ist oder anders gesagt wird als ein beliebiges Wort der LängeA=(X,Q,q0,F,δ)kk>0wXk{δ(q,w):qQ}wk Die letzten k Symbole bestimmen den Zustand, zu dem es führt.>kk

Wenn nun ein Automat lokal ist, muss er für einige k ' < k nicht k ' -lokal sein , sondern muss für k ' > k k ' -lokal sein, da die letzten Symbole eines Wortes | w | > k Bestimmen Sie den Zustand, falls vorhanden, eindeutig.kkk<kkk>k|w|>k

Jetzt versuche ich, die Anzahl der Zustände und die Lokalität eines Automaten zu verbinden. Ich vermute:k

Lemma: Let sein k -local, wenn | Q | < k dann ist der Automat auch | Q | -lokal.A=(X,Q,q0,F,δ)k|Q|<k|Q|

Aber ich habe keine Beweise oder Ideen bewiesen?

Ich hoffe , dieses Lemma herzuleiten etwas über die Anzahl der Zustände eines Automaten , die nicht ist -local für alle k N bei einer festen N > 0 , aber k -local für einige k > N .kkNN>0kk>N

StefanH
quelle

Antworten:

7

Da Sie sagen , dass sollte höchstens ein Element, werde ich davon ausgehen , dass Sie die Version von DFA verwenden , wo δ teilweise sein kann. Dann ist dies ein Gegenbeispiel: X = { a , b } , Q = { 0 , 1 , 2 , 3 , 4 } , δ ( q , a ) =Tw:={δ(q,w):qQ}δ für q < 4 und δ ( 1 , b ) = 2 , δ ( 2 , b ) = 3 , δ ( 4 , b ) = 0 . F und q 0 spielen für diese Frage offensichtlich keine Rolle.X={a,b},Q={0,1,2,3,4},δ(q,a)=q+1q<4δ(1,b)=2,δ(2,b)=3,δ(4,b)=0Fq0

Der Automat ist lokal, aber nicht 5- lokal, da T a b a a b = { 0 , 3 } .65Tabaab={0,3}

Bearbeiten: Dieses Gegenbeispiel funktioniert nicht, ich werde es behalten, damit die Kommentare Sinn machen. Das Folgende tut es jedoch.

Nehmen Sie mit den Übergängen 0 1 ( a ) , 1 2 ( a ) , 2 3 ( a ) , 2 0 ( b ) , 3 2 ( b ) . Dieser Automat ist 5X={a,b},Q={0,1,2,3}01(a),12(a),23(a),20(b),32(b)5-lokal, aber nicht -lokal: für a a b a erhalten wir die Pfade 0 1 2 0 1 und 1 2 3 2 3 , dh T a a b a = { 1 , 3 } .4aaba0120112323Taaba={1,3}

Klaus Draeger
quelle
Mit Ihren Automaten stimmt etwas nicht. Haben Sie bestimmte Übergänge vergessen? Das Wort führt zu keinem Zustand, unabhängig davon, wo ich anfange ...abaab
StefanH
01(a),12(a,b),23(a,b),34(a),40(b)abaab und 3 4 0 1 2 3 . 012340340123
Klaus Draeger
Entschuldigung, du hast recht!
StefanH
Oh, eigentlich bin ich nicht, aber aus einem anderen Grund. Sie erhalten diese Pfade, aber dann können Sie unbestimmte Zeit wiederholen - dieser Automat ist für kein k k- lokal . abaabkk
Klaus Draeger
p,qwδ(p,w)=pδ(q,w)=q
8

Eine späte Antwort, aber die an die Synchronisation gebundene Verzögerung wurde für mehrere Klassen von Automaten untersucht: siehe zum Beispiel Eindeutige Automaten; Béal et al. MCS'08 .

Ω(|Q|2)O(|Q|2)

kk

Joseph Stack
quelle
Sie scheinen zu implizieren, dass die Synchronisationsverzögerung k-local entspricht ....?
vzn
1
kk
Eine gute Antwort lässt wichtige Details nicht aus. es ist möglich, dass sie (fast? genau?) gleichwertig sind, aber dann wäre dies eine neue "Brücke thm", nicht in einem Artikel oder einer veröffentlichten Verbindung ...? wenn ja, muss es irgendwo genauer ausgearbeitet werden ...
vzn
1
Okay. Ich habe die Antwort bearbeitet, um den Punkt zu betonen. Ich glaube nicht, dass eine Brücke benötigt wird, die über die Überprüfung der Definition hinausgeht.
Joseph Stack
schlagen vor, dass beide Definitionen genau angegeben und dann als gleichwertig erwiesen werden. Danke zur Klarstellung.
VZN