Eine binäre Relation zwischen Zuständen zustandsbasierter Systeme (Kripke‑Modelle, beschriftete Übergangssysteme, Prozesse), die ihr beobachtbares Verhalten Schritt für Schritt abgleicht: Immer wenn verbundene Zustände eine Transition mit Label a ausführen, kann der verbundene Partner mit einer a‑Transition zu verwandten Zielzuständen nachziehen, und umgekehrt; Bisimulationsäquivalenz (Bisimilarität) bedeutet, dass eine solche Relation die Zustände verbindet.

Prinzip

Wahrung der Ununterscheidbarkeit bezüglich der gewählten Beobachtungssprache durch Forderung eines hin‑und‑her‑Abgleichs der Übergänge (und der Kennzeichnungs­eigenschaften), sodass modale und bisimulationsinvariante Eigenschaften bisimilaren Zuständen nicht unterscheiden können.

Demonstration

Zwei Kripke‑Modelle sind bisimilar, wenn es eine Relation gibt, die ihre Anfangszustände verbindet, wobei propositional Bewertungen übereinstimmen und für jeden Nachfolger in einem Modell ein entsprechender Nachfolger im anderen existiert; modale Formeln, die im einen Anfangszustand wahr sind, sind auch im anderen wahr.

Fehlanwendung

Bisimulation fahrlässig als Äquivalenzbeweis für Systeme mit quantitativen, probabilistischen, zeitlichen oder ressourcen­sensitiven Merkmalen verwenden, ohne die entsprechenden quantitativen bzw. probabilistischen Bisimulationsdefinitionen zu übernehmen; oder aus Bisimilarität Isomorphie folgern, obwohl Verästelungsunterschiede bestehen.

Konsequenz

Bisimulation liefert verhaltensmäßige Äquivalenz, die die Invarianz modal formulierbarer Eigenschaften garantiert; sie unterstützt Minimierung und Quotientbildung von Modellen, Kongruenzbegründung in Prozesskalkülen und kompositionale Verifikationsmethoden.

Umkehrung

Die Umkehr führt zur Simulation: Eine Simulationsrelation verlangt lediglich einseitiges Nachziehen (ein System simuliert ein anderes) und ergibt einen Präordnungscharakter statt einer Äquivalenz; diese Perspektivumkehr betont beobachtbare Verfeinerungen statt vollständiger Verhaltensidentität.

Abgrenzung

Standard‑Bisimulation gilt für beschriftete Übergangssysteme und Kripke‑Rahmen mit booleschen Beobachtungen; sie muss für probabilistische, stochastische, zeitliche, hybride oder quantitative Systeme angepasst werden und fokussiert die Verästelungsstruktur statt linearer Trace‑Äquivalenz.

Semantische Spannung

Spannung besteht zwischen Bisimulation und Trace‑Äquivalenz: Trace‑Äquivalenz ignoriert Verästelung und ist schwächer, während Bisimulation stärker, aber manchmal zu diskriminierend für beobachtbare Spezifikationen ist; außerdem besteht Spannung zwischen starker Bisimulation und schwächeren Varianten (branching, weak, observational), die interne Schritte abstrahieren.

Synthese

Bisimulation ist die schrittweise hin‑und‑her‑Abgleichrelation, die Verhaltensununterscheidbarkeit in verzweigten Modellen erfasst: Durch symmetrisches Nachziehen von Aktionen und Beobachtungen begründet sie modale Invarianz, Modellreduktion und kompositionales Schließen, mit Varianten für unterschiedliche quantitative Systemeigenschaften.