Bisimulation and Bisimilarity #
A bisimulation is a binary relation on the states of two LTSs, which establishes a tight semantic
correspondence. More specifically, if two states s₁ and s₂ are related by a bisimulation, then
s₁ can mimic all transitions of s₂ and vice versa. Furthermore, the derivatives reached through
these transitions remain related by the bisimulation.
Bisimilarity is the largest bisimulation between two LTSs: it relates any two states that are related by some bisimulation between those LTSs.
Weak bisimulation (resp. bisimilarity) is the relaxed version of bisimulation (resp. bisimilarity) whereby internal actions performed by processes can be ignored.
For an introduction to theory of bisimulation, we refer to [Sangiorgi2011].
Main definitions #
IsBisimulation lts₁ lts₂ r: the relationris a bisimulation betweenlts₁andlts₂.Bisimilarity lts₁ lts₂: states related by some bisimulation betweenlts₁andlts₂.bisimulationStep lts₁ lts₂: the monotone one-step bisimulation operator.BisimilarityApprox lts₁ lts₂ o: the stratum of bisimilarity at an index inWithTop Ordinal.UpToHomBisimilarity lts₁ lts₂ r: the closure ofrunder bisimilarity in each LTS.IsBisimulationUpTo lts₁ lts₂ r: transitions from states related byrcan be matched with derivatives inUpToHomBisimilarity lts₁ lts₂ r.IsWeakBisimulation lts₁ lts₂ r: the relationris a weak bisimulation.WeakBisimilarity lts₁ lts₂: states related by some weak bisimulation.IsSWBisimulation lts₁ lts₂ r: a characterization of weak bisimulation using single-transition challenges, which we prove to be sound and complete.
The Hom variants specialize these definitions to comparing states in the same LTS.
Notations #
s₁ ~[lts₁,lts₂] s₂: the statess₁ands₂are bisimilar underlts₁andlts₂.s₁ ≈[lts₁,lts₂] s₂: the statess₁ands₂are weakly bisimilar underlts₁andlts₂.s₁ ~[lts] s₂ands₁ ≈[lts] s₂: the corresponding homogeneous relations.s₁ ~[lts₁,lts₂;o] s₂ands₁ ~[lts;o] s₂: approximations of bisimilarity. Ordinals and natural numbers coerce toWithTop Ordinal;open scoped Ordinalenablesω. The index⊤denotes the intersection of all ordinal strata.
Main statements #
LTS.IsBisimulation.inv: the inverse of a bisimulation is a bisimulation.HomBisimilarity.eqv: homogeneous bisimilarity is an equivalence relation (seeEquivalence).Bisimilarity.isBisimulation: bisimilarity is itself a bisimulation.BisimilarityApprox.top_eq_bisimilarity: the top endpoint is bisimilarity for all LTSs.BisimilarityApprox.omega_eq_bisimilarity: on image-finite LTSs, the omega approximation is bisimilarity.BisimilarityApprox.stabilizes: the ordinal strata eventually stabilize at bisimilarity.IsBisimulation.le_bisimilarity: bisimilarity is the largest bisimulation.Bisimilarity.gfp: the union of bisimilarity and any bisimulation is equal to bisimilarity.LTS.IsBisimulationUpTo.isBisimulation: ifris a bisimulation up to bisimilarity,UpToHomBisimilarity lts₁ lts₂ ris a bisimulation.LTS.IsBisimulationUpTo.le_bisimilarity: a bisimulation up to bisimilarity relates only bisimilar states.LTS.IsBisimulation.traceEq: any bisimulation that relates two states implies that they are trace equivalent (seeTraceEq).Bisimilarity.deterministic_bisim_eq_traceEq: in a deterministic LTS, bisimilarity and trace equivalence coincide.HomBisimilarity.symm_simulation: homogeneous bisimilarity can be characterized through symmetric simulations.WeakBisimilarity.weakBisim_eq_swBisim: weak bisimulation and sw-bisimulation coincide.HomWeakBisimilarity.eqv: homogeneous weak bisimilarity is an equivalence relation.
A relation is a bisimulation if, whenever it relates two states, the transitions originating from these states mimic each other and the reached derivatives are themselves related.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Relation to simulation #
Any bisimulation is also a simulation.
The inverse of a bisimulation is a simulation.
Helper for following a transition by the first state in a pair of a Bisimulation.
Helper for following a transition by the second state in a pair of a Bisimulation.
If the unique transition of a state is matched by a related state in a bisimulation, then the derivatives are still in the bisimulation.
If the unique transition of a state is matched by a related state in the inverse of a bisimulation, then the derivatives are still in the bisimulation.
If a state is deterministic for μ, then any transition made by a related state in a
bisimulation is matched by a unique transition (left variant).
If a state is deterministic for μ, then any transition made by a related state in a
bisimulation is matched by a unique transition (right variant).
A homogeneous bisimulation is a bisimulation where the underlying LTSs are the same.
Equations
- lts.IsHomBisimulation = lts.IsBisimulation lts
Instances For
Two states are bisimilar if they are related by some bisimulation.
Equations
- lts₁.Bisimilarity lts₂ s₁ s₂ = ∃ (r : State₁ → State₂ → Prop), r s₁ s₂ ∧ lts₁.IsBisimulation lts₂ r
Instances For
Notation for bisimilarity.
Differently from standard pen-and-paper presentations, we require the LTSs to be mentioned explicitly.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Homogeneous bisimilarity is bisimilarity where the underlying LTSs are the same.
Equations
- lts.HomBisimilarity = lts.Bisimilarity lts
Instances For
Notation for homogeneous bisimilarity.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Helper for following a transition by the first state in a pair of a Bisimilarity.
Helper for following a transition by the first state in a pair of a Bisimilarity.
Homogeneous bisimilarity is reflexive.
States with the same image function are bisimilar.
The inverse of a bisimulation is a bisimulation.
Bisimilarity is symmetric.
The composition of two bisimulations is a bisimulation.
Bisimilarity is transitive.
Homogeneous bisimilarity is an equivalence relation.
Bisimulation implies simulation equivalence.
The union of two bisimulations is a bisimulation.
Bisimilarity is a bisimulation.
Bisimilarity is the largest bisimulation.
The union of bisimilarity with any bisimulation is bisimilarity.
calc support for bisimilarity.
Equations
- Cslib.LTS.instTransBisimilarity = { trans := ⋯ }
Stratification of bisimilarity #
Following [Sangiorgi2011], the strata start with the universal relation and require matching
transitions into the preceding stratum at successors. Limit ordinals intersect earlier strata;
the added top ordinal ⊤ intersects all ordinal strata and equals bisimilarity.
The greatest fixed point of the one-step operator is bisimilarity.
The approximation of bisimilarity indexed by ordinals with an added top endpoint.
Ordinal stages use OrdinalApprox.gfpApprox; at ⊤ we intersect all ordinal stages,
corresponding to the infinity approximation in [Sangiorgi2011].
Equations
- One or more equations did not get rendered due to their size.
Instances For
Infix notation for the ordinal-indexed approximation of bisimilarity of two states.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The ordinal-indexed approximation of bisimilarity within one LTS.
Equations
- lts.HomBisimilarityApprox o = lts.BisimilarityApprox lts o
Instances For
Infix notation for the ordinal-indexed approximation of homogeneous bisimilarity.
Equations
- One or more equations did not get rendered due to their size.
Instances For
At an ordinal index, the approximation is mathlib's greatest-fixed-point approximant.
The top endpoint intersects all ordinal strata.
Membership at the top endpoint means membership at every ordinal stage.
The intersection of all ordinal strata is bisimilarity, for arbitrary LTSs.
A successor stratum applies the one-step operator to the preceding stratum.
Every pair of states belongs to the zeroth stratum.
Membership in a successor stratum is given by matching transitions into the previous one.
Follow a transition by the first state, consuming one level of approximation.
Follow a transition by the second state, consuming one level of approximation.
The strata decrease with the ordinal index.
The restriction to natural-number indices is decreasing.
Membership in a stratum implies membership in every earlier stratum.
BisimilarityApprox.of_ge for natural number indices.
Each successor stratum is contained in the preceding stratum.
The omega stratum is the intersection of the finite strata.
Bisimilar states belong to every ordinal stratum.
For all LTSs, some ordinal stratum coincides with bisimilarity.
Once a stratum reaches bisimilarity, every later stratum equals bisimilarity.
The ordinal stratification eventually stabilizes at bisimilarity.
Each ordinal stratum is symmetric.
Ordinal strata compose across LTSs in a common state universe at the same ordinal index.
Finite strata compose even when the state types inhabit different universes.
Homogeneous ordinal strata are reflexive.
Each homogeneous ordinal stratum is an equivalence relation.
If the second LTS is image-finite, the omega approximation is a simulation.
If the first LTS is image-finite, the inverse of the omega approximation is a simulation.
On image-finite LTSs, the omega approximation is a bisimulation. This is the image-finite stratification result in [Sangiorgi2011].
If the second LTS is image-finite, a transition by the first state has a matching derivative related at every finite depth.
If the first LTS is image-finite, a transition by the second state has a matching derivative related at every finite depth.
On image-finite LTSs, membership in every finite stratum implies bisimilarity.
On image-finite LTSs, membership in the omega approximation is bisimilarity.
On image-finite LTSs, the omega approximation coincides with bisimilarity.
On image-finite LTSs, every stratum at or beyond omega is bisimilarity.
On image-finite LTSs, membership in any stratum at or beyond omega is bisimilarity.
Order properties #
Bisimulations equipped with union form a join-semilattice.
Equations
- One or more equations did not get rendered due to their size.
The empty (heterogeneous) relation is a bisimulation.
Equations
- Cslib.LTS.instTopSubtypeForallForallPropIsBisimulation = { top := ⟨fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2, ⋯⟩ }
In the inclusion order on bisimulations:
- The empty relation is the bottom element.
- Bisimilarity is the top element.
Equations
- One or more equations did not get rendered due to their size.
Bisimulation up-to #
The closure of r under bisimilarity in each LTS: s₁ and s₂ are related if there are
t₁ and t₂ with s₁ ~[lts₁] t₁, r t₁ t₂, and t₂ ~[lts₂] s₂.
Equations
- lts₁.UpToHomBisimilarity lts₂ r = Relation.Comp (fun (x1 x2 : State₁) => lts₁.HomBisimilarity x1 x2) (Relation.Comp r fun (x1 x2 : State₂) => lts₂.HomBisimilarity x1 x2)
Instances For
A relation r is a bisimulation up to homogeneous bisimilarity if, whenever it relates two
states, their transitions can be matched with derivatives related by
UpToHomBisimilarity lts₁ lts₂ r.
Equations
- One or more equations did not get rendered due to their size.
Instances For
If r is a bisimulation up to bisimilarity, its closure
UpToHomBisimilarity lts₁ lts₂ r is a bisimulation.
A bisimulation up to bisimilarity relates only bisimilar states.
If two states are related by a bisimulation, they can mimic each other's multi-step transitions.
Relation to trace equivalence #
Any bisimulation implies trace equivalence.
In general, trace equivalence is not a bisimulation (extra conditions are needed, see for
example Bisimulation.deterministic_trace_eq_is_bisim).
In general, bisimilarity and trace equivalence are distinct.
In any deterministic LTS, trace equivalence is a bisimulation.
In deterministic LTSs, trace equivalence implies bisimilarity.
In a deterministic lts, bisimilarity, trace equivalence, and simulation equivalence are equivalent to one-another.
In deterministic LTSs, bisimilarity and trace equivalence coincide.
Homogeneous bisimilarity can also be characterized through symmetric simulations.
Weak bisimulation and weak bisimilarity #
A weak bisimulation is similar to a Bisimulation, but allows for the related processes to do
internal work. Technically, this is defined as a Bisimulation on the saturation of the LTSs.
Equations
- lts₁.IsWeakBisimulation lts₂ r = lts₁.saturate.IsBisimulation lts₂.saturate r
Instances For
A homogeneous bisimulation is a bisimulation where the underlying LTSs are the same.
Equations
- lts.IsHomWeakBisimulation = lts.IsWeakBisimulation lts
Instances For
Two states are weakly bisimilar if they are related by some weak bisimulation.
Equations
- lts₁.WeakBisimilarity lts₂ s₁ s₂ = ∃ (r : State₁ → State₂ → Prop), r s₁ s₂ ∧ lts₁.IsWeakBisimulation lts₂ r
Instances For
Notation for weak bisimilarity.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Homogeneous bisimilarity is bisimilarity where the underlying LTSs are the same.
Equations
- lts.HomWeakBisimilarity = lts.WeakBisimilarity lts
Instances For
Notation for homogeneous bisimilarity.
Equations
- One or more equations did not get rendered due to their size.
Instances For
An SWBisimulation is a more convenient definition of weak bisimulation, because the challenge
is a single transition. We prove later that this technique is sound, following a strategy inspired
by [Sangiorgi2011].
Equations
- One or more equations did not get rendered due to their size.
Instances For
We can now prove that any relation is a WeakBisimulation iff it is an SWBisimulation.
This formalises lemma 4.2.10 in [Sangiorgi2011].
Weak bisimilarity can also be characterized through sw-bisimulations.
Homogeneous weak bisimilarity is reflexive.
The inverse of a weak bisimulation is a weak bisimulation.
Weak bisimilarity is symmetric.
The composition of two weak bisimulations is a weak bisimulation.
The composition of two sw-bisimulations is an sw-bisimulation.
Weak bisimilarity is transitive.
Homogeneous weak bisimilarity is an equivalence relation.