Wann sind zwei Simulationen keine Bisimulation?

20

Bei einem markierten Übergangssystem ist eine Menge von Zuständen, eine Menge von Markierungen und eine ternäre Beziehung. Schreiben Sie wie üblich für . Der markierte Übergang dass das System im Zustand Zustand mit label \ alpha in q ändert , was bedeutet, dass \ alpha eine beobachtbare Aktion ist, die die Zustandsänderung verursacht.S Λ S × Λ × S p α Q ( p , α , Q ) p α q p q α α(S,Λ,)SΛ→⊆S×Λ×Spαq(p,α,q)∈→pαqpqαα

Nun heißt eine Relation RS×S eine Simulation iff

(p,q)R, if pαp then q,qαq and (p,q)R.

Eine LTS soll eine andere simulieren, wenn zwischen ihnen eine Simulationsbeziehung besteht.

In ähnlicher Weise ist eine Beziehung eine Bisimulation, fallsRS×S wenn  p(p,q)R,

 if pαp then q,qαq and (p,q)R and  if qαq then p,pαp and (p,q)R.

Zwei LTS gelten als bisimilar, wenn zwischen ihren Zustandsräumen eine Bisimulation besteht.

Es ist klar, dass diese beiden Begriffe durchaus verwandt sind, aber sie sind nicht gleich.

Unter welchen Bedingungen simuliert ein LTS ein anderes und umgekehrt, aber die beiden LTS sind nicht so ähnlich?

Dave Clarke
quelle

Antworten:

12

Da ein CCS-Prozess mehr als tausend Pixel wert ist und die zugrunde liegende LTS leicht zu erkennen ist, gibt es zwei Prozesse, die sich gegenseitig simulieren, jedoch nicht so ähnlich sind:

Q = a b

P=ab+a
Q=ab

ist eine Simulation.R1={(ab+a,ab),(b,b),(0,b),(0,0)}

ist eine Simulation.R2={(ab,ab+a),(b,b),(0,0)}

und Q R 2 P, aber P und Q sind nicht gleich. Warum nicht? Da P a 0 und die einzige , Q ' , so dass Q ein Q ' ist b ... und 0 ist nicht bisimular zu b .P R1 QQ R2 PPQPa0QQaQb0b

Warum können sie sich dann gegenseitig simulieren? Weil Q simuliert, weil es alles kann, was Q tut. Und Q simuliert P, denn selbst wenn P in einem Schritt zu einem Programm gehen kann, das nichts tut, kann Q das immer noch in einem Schritt tun , und das ist alles, was es braucht, um etwas zu simulieren. Der Hauptunterschied zur Bisimulation besteht darin, dass Sie, wie Charles sagte, dieselben Prozesse mit beiden Simulationen in Beziehung setzen müssen. (dh R so, dass sowohl R als auch R - 1 Simulationen sind)PQQQPPaQaRRR1

jmad
quelle
10

Selbst wenn es in jeder Richtung eine Simulation gibt, beziehen sich die Vorwärts- und Rückwärtssimulationen möglicherweise nicht auf die gleichen Sätze von Zuständen. Manchmal haben Sie eine Simulation in einer Richtung und eine Simulation R 2 in der anderen Richtung und zwei Zustände p 1 und q, die durch R 1, aber nicht durch R 2 oder eine andere Simulation in derselben Richtung zusammenhängen.R1R2p1qR1R2

Das kanonische Beispiel sind zwei Systeme, die die gleichen Spuren haben, aber unterschiedliche Entscheidungen treffen . Stellen Sie sich zwei Getränkeautomaten vor: Die erste (die böse) nimmt eine Münze ( c) und entscheidet nicht deterministisch, ob sie eine Tasse Tee liefert ( t). Die zweite Maschine (die Gute) nimmt eine Münze ( c) und liefert eine Tasse Tee ( t).

early and late choice

Die gute Maschine simuliert die böse Maschine: nimm . Alle ausgehenden Zustandsübergänge werden abgedeckt, einschließlich r (das keinen ausgehenden Übergang hat, also ist es trivial). Beachten Sie, wie die gute Maschine den Unterschied zwischen r und p vergisst .R1={(s,s),(p,p),(q,q),(r,p)}rrp

Die böse Maschine simuliert die gute Maschine: nimm . Der Zustand r wird von dieser Simulation nicht verwendet. Tatsächlich ist es für eine Simulation nicht möglich, r zu verwenden , da s ' auf einen Zustand abgebildet werden muss, ab dem eine Spur der Länge 2 möglich ist, also muss es s sein ; p ' muss auf einen Nachfolger von s abbildenR2={(s,s),(p,p),(q,q)}rrs2sp Mit dem Label c , also ist es p oder r , aber dieser Zustand muss auch eine mögliche Spur der Länge 1 haben , also muss es p sein ; und aus der gleichen Überlegungmuss q ' auf q abbilden, wobei keine Möglichkeit übrig bleibt, irgendeinen Zustand auf r abzubilden.scpr1pqqr

Ein simuation in eine Richtung muss senden irgendwo. Eine Simulation in die andere Richtung muss r vermeiden . Daher gibt es keine Beziehung, die eine Simulation in beide Richtungen darstellt: Die Systeme sind nicht bisimilar.rr

Der Unterschied zwischen den beiden Maschinen besteht darin, dass die gute Maschine deterministisch ist und (unter der Annahme, dass sie lebhaft ist) immer Tee liefert, wenn Sie eine Münze einwerfen, während die böse Maschine aus einer Laune heraus die Münze nehmen kann, aber stecken bleibt und keinen Tee liefern kann.

Diese Art von Unterschied tritt häufig bei der Untersuchung von gleichzeitigen Systemen auf. Die Antwort von jmad zeigt einen CCS-Prozess mit diesem LTS.

Für weitere Informationen über Bisimulationen empfehle ich Davide Sangiorgis Notizen zu den Ursprüngen der Bisimulation und der Koinduktion . (Dies ist Übung 1, S. 29, und die Notizen verwenden dasselbe Beispiel.)

Gilles 'SO - hör auf böse zu sein'
quelle
Die Tatsache, dass Zwei-Wege-Simulationen nicht der gleichen Ähnlichkeit entsprechen, legt für mich nahe, dass Simulation nicht die richtige Idee der Annäherung in Gegenwart von Nichtdeterminismus ist. Gibt es noch andere Ideen, die in Betracht gezogen wurden?
Uday Reddy
2

Gilles' Antwort ist sehr gut und formal, und in der Tat, wenn durch simuliert L T S 2 mit einer Relation R und L T S 2 wird simuliert durch L T S 1 mit dem inversen von R , dann R ist eine Bisimulation.LTS1LTS2RLTS2LTS1RR

LTS1LTS2RLTS2LTS1R

Charles
quelle
Ich denke, was ich damit sagen will, ist, dass eigentlich immer zwei LTSs bisimilar sind. Die eigentliche Frage ist also eher, ob eine bestimmte Beziehung eine (bi) Simulation ist.
Charles