Documentation

Cslib.Foundations.Semantics.LTS.Bisimulation

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 #

The Hom variants specialize these definitions to comparing states in the same LTS.

Notations #

Main statements #

def Cslib.LTS.IsBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) (r : State₁ → State₂ → Prop) :

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 #

    theorem Cslib.LTS.IsBisimulation.isSimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} :
    lts₁.IsBisimulation lts₂ r → lts₁.IsSimulation lts₂ r

    Any bisimulation is also a simulation.

    theorem Cslib.LTS.IsBisimulation.flip_isSimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} :
    lts₁.IsBisimulation lts₂ r → lts₂.IsSimulation lts₁ (flip r)

    The inverse of a bisimulation is a simulation.

    theorem Cslib.LTS.IsBisimulation.isSimulation_iff {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} :
    lts₁.IsBisimulation lts₂ r ↔ lts₁.IsSimulation lts₂ r ∧ lts₂.IsSimulation lts₁ (flip r)

    A relation is a bisimulation iff both it and its inverse are simulations.

    theorem Cslib.LTS.IsBisimulation.follow_fst {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (htr : lts₁.Tr s₁ μ s₁') :
    ∃ (s₂' : State₂), lts₂.Tr s₂ μ s₂' ∧ r s₁' s₂'

    Helper for following a transition by the first state in a pair of a Bisimulation.

    theorem Cslib.LTS.IsBisimulation.follow_snd {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₂' : State₂} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (htr : lts₂.Tr s₂ μ s₂') :
    ∃ (s₁' : State₁), lts₁.Tr s₁ μ s₁' ∧ r s₁' s₂'

    Helper for following a transition by the second state in a pair of a Bisimulation.

    theorem Cslib.LTS.IsBisimulation.match_deterministic {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} {s₂' : State₂} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (hdet : lts₁.DeterministicStateLabel s₁ μ) (htr₁ : lts₁.Tr s₁ μ s₁') (htr₂ : lts₂.Tr s₂ μ s₂') :
    r s₁' s₂'

    If the unique transition of a state is matched by a related state in a bisimulation, then the derivatives are still in the bisimulation.

    theorem Cslib.LTS.IsBisimulation.match_deterministic₂ {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} {s₂' : State₂} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (hdet : lts₂.DeterministicStateLabel s₂ μ) (htr₁ : lts₁.Tr s₁ μ s₁') (htr₂ : lts₂.Tr s₂ μ s₂') :
    r s₁' s₂'

    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.

    theorem Cslib.LTS.IsBisimulation.follow_fst_deterministic {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (hdet : lts₂.DeterministicStateLabel s₂ μ) (htr : lts₁.Tr s₁ μ s₁') :
    ∃! s₂' : State₂, lts₂.Tr s₂ μ s₂' ∧ r s₁' s₂'

    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).

    theorem Cslib.LTS.IsBisimulation.follow_snd_deterministic {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₂' : State₂} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (hdet : lts₁.DeterministicStateLabel s₁ μ) (htr : lts₂.Tr s₂ μ s₂') :
    ∃! s₁' : State₁, lts₁.Tr s₁ μ s₁' ∧ r s₁' s₂'

    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).

    @[reducible, inline]
    abbrev Cslib.LTS.IsHomBisimulation {Label : Type u_3} {State : Type u_4} (lts : LTS State Label) (r : State → State → Prop) :

    A homogeneous bisimulation is a bisimulation where the underlying LTSs are the same.

    Equations
    Instances For
      def Cslib.LTS.Bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
      State₁ → State₂ → Prop

      Two states are bisimilar if they are related by some bisimulation.

      Equations
      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
          @[reducible, inline]
          abbrev Cslib.LTS.HomBisimilarity {Label : Type u_3} {State : Type u_4} (lts : LTS State Label) :
          State → State → Prop

          Homogeneous bisimilarity is bisimilarity where the underlying LTSs are the same.

          Equations
          Instances For

            Notation for homogeneous bisimilarity.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              theorem Cslib.LTS.Bisimilarity.follow_fst {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} (hr : lts₁.Bisimilarity lts₂ s₁ s₂) (htr : lts₁.Tr s₁ μ s₁') :
              ∃ (s₂' : State₂), lts₂.Tr s₂ μ s₂' ∧ lts₁.Bisimilarity lts₂ s₁' s₂'

              Helper for following a transition by the first state in a pair of a Bisimilarity.

              theorem Cslib.LTS.Bisimilarity.follow_snd {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₂' : State₂} (hr : lts₁.Bisimilarity lts₂ s₁ s₂) (htr : lts₂.Tr s₂ μ s₂') :
              ∃ (s₁' : State₁), lts₁.Tr s₁ μ s₁' ∧ lts₁.Bisimilarity lts₂ s₁' s₂'

              Helper for following a transition by the first state in a pair of a Bisimilarity.

              theorem Cslib.LTS.HomBisimilarity.refl {State : Type u_4} {Label✝ : Type u_5} {lts : LTS State Label✝} (s : State) :

              Homogeneous bisimilarity is reflexive.

              theorem Cslib.LTS.HomBisimilarity.of_image_eq {Label : Type u_3} {State : Type u_4} {lts : LTS State Label} {s₁ s₂ : State} (h : lts.image s₁ = lts.image s₂) :
              lts.HomBisimilarity s₁ s₂

              States with the same image function are bisimilar.

              theorem Cslib.LTS.IsBisimulation.inv {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} (h : lts₁.IsBisimulation lts₂ r) :
              lts₂.IsBisimulation lts₁ (flip r)

              The inverse of a bisimulation is a bisimulation.

              theorem Cslib.LTS.Bisimilarity.symm {Label : Type u_3} {State₁ : Type u_4} {State₂ : Type u_5} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} (h : lts₁.Bisimilarity lts₂ s₁ s₂) :
              lts₂.Bisimilarity lts₁ s₂ s₁

              Bisimilarity is symmetric.

              theorem Cslib.LTS.IsBisimulation.comp {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r1 : State₁ → State₂ → Prop} {State✝ : Type u_4} {lts₃ : LTS State✝ Label} {r2 : State₂ → State✝ → Prop} (h1 : lts₁.IsBisimulation lts₂ r1) (h2 : lts₂.IsBisimulation lts₃ r2) :
              lts₁.IsBisimulation lts₃ (Relation.Comp r1 r2)

              The composition of two bisimulations is a bisimulation.

              theorem Cslib.LTS.Bisimilarity.trans {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {State✝ : Type u_4} {lts₃ : LTS State✝ Label} {s₃ : State✝} (h1 : lts₁.Bisimilarity lts₂ s₁ s₂) (h2 : lts₂.Bisimilarity lts₃ s₂ s₃) :
              lts₁.Bisimilarity lts₃ s₁ s₃

              Bisimilarity is transitive.

              theorem Cslib.LTS.HomBisimilarity.eqv {State✝ : Type u_4} {Label✝ : Type u_5} {lts : LTS State✝ Label✝} :
              Equivalence fun (x1 x2 : State✝) => lts.HomBisimilarity x1 x2

              Homogeneous bisimilarity is an equivalence relation.

              instance Cslib.LTS.instIsEquivHomBisimilarity {State : Type u_4} {Label✝ : Type u_5} {lts : LTS State Label✝} :
              IsEquiv State fun (x1 x2 : State) => lts.HomBisimilarity x1 x2
              theorem Cslib.LTS.IsBisimulation.simulationEquiv {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} (h : lts₁.IsBisimulation lts₂ r) (hrel : r s₁ s₂) :
              lts₁.SimulationEquiv lts₂ s₁ s₂

              Bisimulation implies simulation equivalence.

              theorem Cslib.LTS.IsBisimulation.sup {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r s : State₁ → State₂ → Prop} (hrb : lts₁.IsBisimulation lts₂ r) (hsb : lts₁.IsBisimulation lts₂ s) :
              lts₁.IsBisimulation lts₂ (r ⊔ s)

              The union of two bisimulations is a bisimulation.

              theorem Cslib.LTS.Bisimilarity.isBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
              lts₁.IsBisimulation lts₂ fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

              Bisimilarity is a bisimulation.

              theorem Cslib.LTS.IsBisimulation.le_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} (h : lts₁.IsBisimulation lts₂ r) :
              r ≤ fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

              Bisimilarity is the largest bisimulation.

              @[simp]
              theorem Cslib.LTS.Bisimilarity.gfp {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (r : State₁ → State₂ → Prop) (h : lts₁.IsBisimulation lts₂ r) :
              (fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2) ⊔ r = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

              The union of bisimilarity with any bisimulation is bisimilarity.

              @[instance_reducible]
              instance Cslib.LTS.instTransBisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {State✝ : Type u_4} {lts₃ : LTS State✝ Label} :
              Trans (fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2) (fun (x1 : State₂) (x2 : State✝) => lts₂.Bisimilarity lts₃ x1 x2) fun (x1 : State₁) (x2 : State✝) => lts₁.Bisimilarity lts₃ x1 x2

              calc support for bisimilarity.

              Equations

              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.

              def Cslib.LTS.bisimulationStep {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
              (State₁ → State₂ → Prop) →o State₁ → State₂ → Prop

              The one-step bisimulation operator.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                theorem Cslib.LTS.isBisimulation_iff_le_bisimulationStep {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} :
                lts₁.IsBisimulation lts₂ r ↔ r ≤ (lts₁.bisimulationStep lts₂) r
                theorem Cslib.LTS.bisimulationStep_gfp {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                OrderHom.gfp (lts₁.bisimulationStep lts₂) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                The greatest fixed point of the one-step operator is bisimilarity.

                def Cslib.LTS.BisimilarityApprox {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
                WithTop Ordinal.{max u_1 u_2} → State₁ → State₂ → Prop

                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
                    @[reducible, inline]
                    abbrev Cslib.LTS.HomBisimilarityApprox {Label : Type u_3} {State : Type u_4} (lts : LTS State Label) (o : WithTop Ordinal.{u_4}) :
                    State → State → Prop

                    The ordinal-indexed approximation of bisimilarity within one LTS.

                    Equations
                    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
                        theorem Cslib.LTS.BisimilarityApprox.coe_eq {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (o : Ordinal.{max u_1 u_2}) :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑o) x1 x2) = OrdinalApprox.gfpApprox (lts₁.bisimulationStep lts₂) ⊤ o

                        At an ordinal index, the approximation is mathlib's greatest-fixed-point approximant.

                        theorem Cslib.LTS.BisimilarityApprox.top_eq_iInf {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ ⊤ x1 x2) = ⨅ (o : Ordinal.{max u_1 u_2}), fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑o) x1 x2

                        The top endpoint intersects all ordinal strata.

                        theorem Cslib.LTS.BisimilarityApprox.top_iff {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} :
                        lts₁.BisimilarityApprox lts₂ ⊤ s₁ s₂ ↔ ∀ (o : Ordinal.{max u_1 u_2}), lts₁.BisimilarityApprox lts₂ (↑o) s₁ s₂

                        Membership at the top endpoint means membership at every ordinal stage.

                        theorem Cslib.LTS.BisimilarityApprox.top_eq_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ ⊤ x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                        The intersection of all ordinal strata is bisimilarity, for arbitrary LTSs.

                        @[simp]
                        theorem Cslib.LTS.BisimilarityApprox.top_iff_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} :
                        lts₁.BisimilarityApprox lts₂ ⊤ s₁ s₂ ↔ lts₁.Bisimilarity lts₂ s₁ s₂

                        Membership at the top endpoint is bisimilarity, for arbitrary LTSs.

                        theorem Cslib.LTS.BisimilarityApprox.zero_eq {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ 0 x1 x2) = ⊤

                        The zeroth stratum is the universal relation.

                        theorem Cslib.LTS.BisimilarityApprox.succ {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {o : WithTop Ordinal.{max u_1 u_2}} :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (o + 1) x1 x2) = (lts₁.bisimulationStep lts₂) fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ o x1 x2

                        A successor stratum applies the one-step operator to the preceding stratum.

                        @[simp]
                        theorem Cslib.LTS.BisimilarityApprox.zero {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} :
                        lts₁.BisimilarityApprox lts₂ 0 s₁ s₂

                        Every pair of states belongs to the zeroth stratum.

                        theorem Cslib.LTS.BisimilarityApprox.succ_iff {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {o : WithTop Ordinal.{max u_1 u_2}} :
                        lts₁.BisimilarityApprox lts₂ (o + 1) s₁ s₂ ↔ ∀ (μ : Label), (∀ (s₁' : State₁), lts₁.Tr s₁ μ s₁' → ∃ (s₂' : State₂), lts₂.Tr s₂ μ s₂' ∧ lts₁.BisimilarityApprox lts₂ o s₁' s₂') ∧ ∀ (s₂' : State₂), lts₂.Tr s₂ μ s₂' → ∃ (s₁' : State₁), lts₁.Tr s₁ μ s₁' ∧ lts₁.BisimilarityApprox lts₂ o s₁' s₂'

                        Membership in a successor stratum is given by matching transitions into the previous one.

                        theorem Cslib.LTS.BisimilarityApprox.follow_fst {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} {o : WithTop Ordinal.{max u_1 u_2}} (h : lts₁.BisimilarityApprox lts₂ (o + 1) s₁ s₂) (htr : lts₁.Tr s₁ μ s₁') :
                        ∃ (s₂' : State₂), lts₂.Tr s₂ μ s₂' ∧ lts₁.BisimilarityApprox lts₂ o s₁' s₂'

                        Follow a transition by the first state, consuming one level of approximation.

                        theorem Cslib.LTS.BisimilarityApprox.follow_snd {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₂' : State₂} {o : WithTop Ordinal.{max u_1 u_2}} (h : lts₁.BisimilarityApprox lts₂ (o + 1) s₁ s₂) (htr : lts₂.Tr s₂ μ s₂') :
                        ∃ (s₁' : State₁), lts₁.Tr s₁ μ s₁' ∧ lts₁.BisimilarityApprox lts₂ o s₁' s₂'

                        Follow a transition by the second state, consuming one level of approximation.

                        theorem Cslib.LTS.BisimilarityApprox.antitone {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        Antitone fun (o : WithTop Ordinal.{max u_1 u_2}) (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ o x1 x2

                        The strata decrease with the ordinal index.

                        theorem Cslib.LTS.BisimilarityApprox.antitone_nat {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        Antitone fun (n : ℕ) (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑n) x1 x2

                        The restriction to natural-number indices is decreasing.

                        theorem Cslib.LTS.BisimilarityApprox.of_ge {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {o o' : WithTop Ordinal.{max u_1 u_2}} (h : lts₁.BisimilarityApprox lts₂ o' s₁ s₂) (hoo' : o ≤ o') :
                        lts₁.BisimilarityApprox lts₂ o s₁ s₂

                        Membership in a stratum implies membership in every earlier stratum.

                        theorem Cslib.LTS.BisimilarityApprox.of_ge_nat {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {m n : ℕ} (h : lts₁.BisimilarityApprox lts₂ (↑n) s₁ s₂) (hmn : m ≤ n) :
                        lts₁.BisimilarityApprox lts₂ (↑m) s₁ s₂

                        BisimilarityApprox.of_ge for natural number indices.

                        theorem Cslib.LTS.BisimilarityApprox.succ_le {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (o : Ordinal.{max u_1 u_2}) :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑o + 1) x1 x2) ≤ fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑o) x1 x2

                        Each successor stratum is contained in the preceding stratum.

                        theorem Cslib.LTS.BisimilarityApprox.limit_iff {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {o : Ordinal.{max u_1 u_2}} (ho : Order.IsSuccLimit o) :
                        lts₁.BisimilarityApprox lts₂ (↑o) s₁ s₂ ↔ ∀ o' < o, lts₁.BisimilarityApprox lts₂ (↑o') s₁ s₂
                        theorem Cslib.LTS.BisimilarityApprox.natCast_eq_iterate {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (n : ℕ) :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑n) x1 x2) = (⇑(lts₁.bisimulationStep lts₂))^[n] ⊤
                        theorem Cslib.LTS.BisimilarityApprox.omega_iff {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} :
                        lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁ s₂ ↔ ∀ (n : ℕ), lts₁.BisimilarityApprox lts₂ (↑n) s₁ s₂

                        The omega stratum is the intersection of the finite strata.

                        theorem Cslib.LTS.Bisimilarity.approx {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} (h : lts₁.Bisimilarity lts₂ s₁ s₂) (o : WithTop Ordinal.{max u_1 u_2}) :
                        lts₁.BisimilarityApprox lts₂ o s₁ s₂

                        Bisimilar states belong to every ordinal stratum.

                        theorem Cslib.LTS.BisimilarityApprox.exists_eq_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
                        ∃ (o : Ordinal.{max u_1 u_2}), (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑o) x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                        For all LTSs, some ordinal stratum coincides with bisimilarity.

                        theorem Cslib.LTS.BisimilarityApprox.eq_bisimilarity_of_le {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {o o' : WithTop Ordinal.{max u_1 u_2}} (hoo' : o ≤ o') (ho : (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ o x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2) :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ o' x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                        Once a stratum reaches bisimilarity, every later stratum equals bisimilarity.

                        theorem Cslib.LTS.BisimilarityApprox.stabilizes {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
                        ∃ (o : Ordinal.{max u_1 u_2}), ∀ (o' : WithTop Ordinal.{max u_1 u_2}), ↑o ≤ o' → (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ o' x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                        The ordinal stratification eventually stabilizes at bisimilarity.

                        theorem Cslib.LTS.BisimilarityApprox.symm {Label : Type u_3} {o : WithTop Ordinal.{max u_4 u_5}} {State₁ : Type u_4} {State₂ : Type u_5} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} (h : lts₁.BisimilarityApprox lts₂ o s₁ s₂) :
                        lts₂.BisimilarityApprox lts₁ o s₂ s₁

                        Each ordinal stratum is symmetric.

                        theorem Cslib.LTS.BisimilarityApprox.trans {Label : Type u_3} {State₁ State₂ State₃ : Type u} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {lts₃ : LTS State₃ Label} {s₁ : State₁} {s₂ : State₂} {s₃ : State₃} {o : WithTop Ordinal.{u}} (h₁ : lts₁.BisimilarityApprox lts₂ o s₁ s₂) (h₂ : lts₂.BisimilarityApprox lts₃ o s₂ s₃) :
                        lts₁.BisimilarityApprox lts₃ o s₁ s₃

                        Ordinal strata compose across LTSs in a common state universe at the same ordinal index.

                        theorem Cslib.LTS.BisimilarityApprox.trans_nat {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {State✝ : Type u_4} {lts₃ : LTS State✝ Label} {s₃ : State✝} {n : ℕ} (h₁ : lts₁.BisimilarityApprox lts₂ (↑↑n) s₁ s₂) (h₂ : lts₂.BisimilarityApprox lts₃ (↑↑n) s₂ s₃) :
                        lts₁.BisimilarityApprox lts₃ (↑n) s₁ s₃

                        Finite strata compose even when the state types inhabit different universes.

                        theorem Cslib.LTS.HomBisimilarityApprox.refl {State : Type u_4} {Label✝ : Type u_5} {lts : LTS State Label✝} (o : WithTop Ordinal.{u_4}) (s : State) :

                        Homogeneous ordinal strata are reflexive.

                        theorem Cslib.LTS.HomBisimilarityApprox.eqv {State✝ : Type u_4} {Label✝ : Type u_5} {lts : LTS State✝ Label✝} (o : WithTop Ordinal.{u_4}) :
                        Equivalence fun (x1 x2 : State✝) => lts.HomBisimilarityApprox o x1 x2

                        Each homogeneous ordinal stratum is an equivalence relation.

                        theorem Cslib.LTS.BisimilarityApprox.trans_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {State✝ : Type u_4} {lts₃ : LTS State✝ Label} {s₃ : State✝} (h₁ : lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁ s₂) (h₂ : lts₂.BisimilarityApprox lts₃ (↑Ordinal.omega0) s₂ s₃) :
                        lts₁.BisimilarityApprox lts₃ (↑Ordinal.omega0) s₁ s₃
                        theorem Cslib.LTS.BisimilarityApprox.isSimulation_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₂.ImageFinite] :
                        lts₁.IsSimulation lts₂ fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) x1 x2

                        If the second LTS is image-finite, the omega approximation is a simulation.

                        theorem Cslib.LTS.BisimilarityApprox.flip_isSimulation_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.ImageFinite] :
                        lts₂.IsSimulation lts₁ (flip fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) x1 x2)

                        If the first LTS is image-finite, the inverse of the omega approximation is a simulation.

                        theorem Cslib.LTS.BisimilarityApprox.isBisimulation_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.ImageFinite] [lts₂.ImageFinite] :
                        lts₁.IsBisimulation lts₂ fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) x1 x2

                        On image-finite LTSs, the omega approximation is a bisimulation. This is the image-finite stratification result in [Sangiorgi2011].

                        theorem Cslib.LTS.BisimilarityApprox.follow_fst_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₁' : State₁} [lts₂.ImageFinite] (h : lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁ s₂) (htr : lts₁.Tr s₁ μ s₁') :
                        ∃ (s₂' : State₂), lts₂.Tr s₂ μ s₂' ∧ lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁' s₂'

                        If the second LTS is image-finite, a transition by the first state has a matching derivative related at every finite depth.

                        theorem Cslib.LTS.BisimilarityApprox.follow_snd_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} {μ : Label} {s₂' : State₂} [lts₁.ImageFinite] (h : lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁ s₂) (htr : lts₂.Tr s₂ μ s₂') :
                        ∃ (s₁' : State₁), lts₁.Tr s₁ μ s₁' ∧ lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁' s₂'

                        If the first LTS is image-finite, a transition by the second state has a matching derivative related at every finite depth.

                        theorem Cslib.LTS.BisimilarityApprox.bisimilarity_of_omega {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} [lts₁.ImageFinite] [lts₂.ImageFinite] (h : lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁ s₂) :
                        lts₁.Bisimilarity lts₂ s₁ s₂

                        On image-finite LTSs, membership in every finite stratum implies bisimilarity.

                        @[simp]
                        theorem Cslib.LTS.BisimilarityApprox.omega_iff_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} [lts₁.ImageFinite] [lts₂.ImageFinite] :
                        lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) s₁ s₂ ↔ lts₁.Bisimilarity lts₂ s₁ s₂

                        On image-finite LTSs, membership in the omega approximation is bisimilarity.

                        theorem Cslib.LTS.BisimilarityApprox.omega_eq_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) [lts₁.ImageFinite] [lts₂.ImageFinite] :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ (↑Ordinal.omega0) x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                        On image-finite LTSs, the omega approximation coincides with bisimilarity.

                        theorem Cslib.LTS.BisimilarityApprox.eq_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.ImageFinite] [lts₂.ImageFinite] {o : WithTop Ordinal.{max u_1 u_2}} (ho : ↑Ordinal.omega0 ≤ o) :
                        (fun (x1 : State₁) (x2 : State₂) => lts₁.BisimilarityApprox lts₂ o x1 x2) = fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                        On image-finite LTSs, every stratum at or beyond omega is bisimilarity.

                        theorem Cslib.LTS.BisimilarityApprox.iff_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {s₁ : State₁} {s₂ : State₂} [lts₁.ImageFinite] [lts₂.ImageFinite] {o : WithTop Ordinal.{max u_1 u_2}} (ho : ↑Ordinal.omega0 ≤ o) :
                        lts₁.BisimilarityApprox lts₂ o s₁ s₂ ↔ lts₁.Bisimilarity lts₂ s₁ s₂

                        On image-finite LTSs, membership in any stratum at or beyond omega is bisimilarity.

                        Order properties #

                        @[instance_reducible]
                        instance Cslib.LTS.instMaxSubtypeForallForallPropIsBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        Max { r : State₁ → State₂ → Prop // lts₁.IsBisimulation lts₂ r }
                        Equations
                        @[simp]
                        theorem Cslib.LTS.coe_sup {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (r s : { r : State₁ → State₂ → Prop // lts₁.IsBisimulation lts₂ r }) :
                        ↑(r ⊔ s) = ↑r ⊔ ↑s
                        @[instance_reducible]
                        instance Cslib.LTS.instSemilatticeSupSubtypeForallForallPropIsBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        SemilatticeSup { r : State₁ → State₂ → Prop // lts₁.IsBisimulation lts₂ r }

                        Bisimulations equipped with union form a join-semilattice.

                        Equations
                        • One or more equations did not get rendered due to their size.
                        theorem Cslib.LTS.IsBisimulation.bot {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :

                        The empty (heterogeneous) relation is a bisimulation.

                        @[instance_reducible]
                        instance Cslib.LTS.instBotSubtypeForallForallPropIsBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        Bot { r : State₁ → State₂ → Prop // lts₁.IsBisimulation lts₂ r }
                        Equations
                        @[instance_reducible]
                        instance Cslib.LTS.instTopSubtypeForallForallPropIsBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        Top { r : State₁ → State₂ → Prop // lts₁.IsBisimulation lts₂ r }
                        Equations
                        @[instance_reducible]
                        instance Cslib.LTS.instBoundedOrderSubtypeForallForallPropIsBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                        BoundedOrder { r : State₁ → State₂ → Prop // lts₁.IsBisimulation lts₂ r }

                        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 #

                        def Cslib.LTS.UpToHomBisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) (r : State₁ → State₂ → Prop) :
                        State₁ → State₂ → Prop

                        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
                        Instances For
                          def Cslib.LTS.IsBisimulationUpTo {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) (r : State₁ → State₂ → Prop) :

                          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
                            theorem Cslib.LTS.IsBisimulationUpTo.isBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} (h : lts₁.IsBisimulationUpTo lts₂ r) :
                            lts₁.IsBisimulation lts₂ (lts₁.UpToHomBisimilarity lts₂ r)

                            If r is a bisimulation up to bisimilarity, its closure UpToHomBisimilarity lts₁ lts₂ r is a bisimulation.

                            theorem Cslib.LTS.IsBisimulationUpTo.le_bisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} (h : lts₁.IsBisimulationUpTo lts₂ r) :
                            r ≤ fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2

                            A bisimulation up to bisimilarity relates only bisimilar states.

                            theorem Cslib.LTS.IsBisimulation.bisim_trace {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) (μs : List Label) (s₁' : State₁) :
                            lts₁.MTr s₁ μs s₁' → ∃ (s₂' : State₂), lts₂.MTr s₂ μs s₂' ∧ r s₁' s₂'

                            If two states are related by a bisimulation, they can mimic each other's multi-step transitions.

                            Relation to trace equivalence #

                            theorem Cslib.LTS.IsBisimulation.traceEq {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} {s₁ : State₁} {s₂ : State₂} (hb : lts₁.IsBisimulation lts₂ r) (hr : r s₁ s₂) :
                            lts₁.TraceEq lts₂ s₁ s₂

                            Any bisimulation implies trace equivalence.

                            theorem Cslib.LTS.Bisimilarity.le_traceEq {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                            (fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2) ≤ lts₁.TraceEq lts₂

                            Bisimilarity is included in trace equivalence.

                            theorem Cslib.LTS.IsBisimulation.traceEq_not_bisim :
                            ∃ (State : Type) (Label : Type) (lts : LTS State Label), ¬lts.IsHomBisimulation lts.HomTraceEq

                            In general, trace equivalence is not a bisimulation (extra conditions are needed, see for example Bisimulation.deterministic_trace_eq_is_bisim).

                            theorem Cslib.LTS.Bisimilarity.bisimilarity_neq_traceEq :
                            ∃ (State : Type) (Label : Type) (lts : LTS State Label), (fun (x1 x2 : State) => lts.HomBisimilarity x1 x2) ≠ lts.HomTraceEq

                            In general, bisimilarity and trace equivalence are distinct.

                            theorem Cslib.LTS.IsBisimulation.deterministic_traceEq_isBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.Deterministic] [lts₂.Deterministic] :
                            lts₁.IsBisimulation lts₂ (lts₁.TraceEq lts₂)

                            In any deterministic LTS, trace equivalence is a bisimulation.

                            theorem Cslib.LTS.Bisimilarity.deterministic_traceEq_bisim {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {s₁ : State₁} {s₂ : State₂} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.Deterministic] [lts₂.Deterministic] (h : lts₁.TraceEq lts₂ s₁ s₂) :
                            lts₁.Bisimilarity lts₂ s₁ s₂

                            In deterministic LTSs, trace equivalence implies bisimilarity.

                            theorem Cslib.LTS.Deterministic.bisim_tfae {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.Deterministic] [lts₂.Deterministic] (s₁ : State₁) (s₂ : State₂) :
                            [lts₁.Bisimilarity lts₂ s₁ s₂, lts₁.TraceEq lts₂ s₁ s₂, lts₁.SimulationEquiv lts₂ s₁ s₂].TFAE

                            In a deterministic lts, bisimilarity, trace equivalence, and simulation equivalence are equivalent to one-another.

                            theorem Cslib.LTS.Bisimilarity.deterministic_bisim_eq_traceEq {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} [lts₁.Deterministic] [lts₂.Deterministic] :
                            (fun (x1 : State₁) (x2 : State₂) => lts₁.Bisimilarity lts₂ x1 x2) = lts₁.TraceEq lts₂

                            In deterministic LTSs, bisimilarity and trace equivalence coincide.

                            theorem Cslib.LTS.HomBisimilarity.symm_simulation {State✝ : Type u_4} {Label✝ : Type u_5} {lts : LTS State✝ Label✝} :
                            (fun (x1 x2 : State✝) => lts.HomBisimilarity x1 x2) = fun (s₁ s₂ : State✝) => ∃ (r : State✝ → State✝ → Prop), r s₁ s₂ ∧ Std.Symm r ∧ lts.IsHomSimulation r

                            Homogeneous bisimilarity can also be characterized through symmetric simulations.

                            Weak bisimulation and weak bisimilarity #

                            def Cslib.LTS.IsWeakBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) (r : State₁ → State₂ → Prop) :

                            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
                            Instances For
                              @[reducible, inline]
                              abbrev Cslib.LTS.IsHomWeakBisimulation {Label : Type u_3} {State : Type u_4} [HasTau Label] (lts : LTS State Label) (r : State → State → Prop) :

                              A homogeneous bisimulation is a bisimulation where the underlying LTSs are the same.

                              Equations
                              Instances For
                                def Cslib.LTS.WeakBisimilarity {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
                                State₁ → State₂ → Prop

                                Two states are weakly bisimilar if they are related by some weak bisimulation.

                                Equations
                                Instances For

                                  Notation for weak bisimilarity.

                                  Equations
                                  • One or more equations did not get rendered due to their size.
                                  Instances For
                                    @[reducible, inline]
                                    abbrev Cslib.LTS.HomWeakBisimilarity {Label : Type u_3} {State : Type u_4} [HasTau Label] (lts : LTS State Label) :
                                    State → State → Prop

                                    Homogeneous bisimilarity is bisimilarity where the underlying LTSs are the same.

                                    Equations
                                    Instances For

                                      Notation for homogeneous bisimilarity.

                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      Instances For
                                        def Cslib.LTS.IsSWBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) (r : State₁ → State₂ → Prop) :

                                        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
                                          theorem Cslib.LTS.IsSWBisimulation.isSimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} [HasTau Label] (h : lts₁.IsSWBisimulation lts₂ r) :
                                          lts₁.IsSimulation lts₂.saturate r
                                          theorem Cslib.LTS.IsSWBisimulation.isSimulation_flip {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} [HasTau Label] (h : lts₁.IsSWBisimulation lts₂ r) :
                                          lts₂.IsSimulation lts₁.saturate (flip r)
                                          theorem Cslib.LTS.IsSWBisimulation.iff_isSimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} [HasTau Label] :
                                          lts₁.IsSWBisimulation lts₂ r ↔ lts₁.IsSimulation lts₂.saturate r ∧ lts₂.IsSimulation lts₁.saturate (flip r)
                                          theorem Cslib.LTS.isWeakBisimulation_iff_isSWBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {r : State₁ → State₂ → Prop} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} :
                                          lts₁.IsWeakBisimulation lts₂ r ↔ lts₁.IsSWBisimulation lts₂ r

                                          We can now prove that any relation is a WeakBisimulation iff it is an SWBisimulation. This formalises lemma 4.2.10 in [Sangiorgi2011].

                                          theorem Cslib.LTS.IsWeakBisimulation.isSwBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} (h : lts₁.IsWeakBisimulation lts₂ r) :
                                          lts₁.IsSWBisimulation lts₂ r
                                          theorem Cslib.LTS.IsSWBisimulation.isWeakBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {r : State₁ → State₂ → Prop} (h : lts₁.IsSWBisimulation lts₂ r) :
                                          lts₁.IsWeakBisimulation lts₂ r
                                          theorem Cslib.LTS.WeakBisimilarity.weakBisim_eq_swBisim {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] (lts₁ : LTS State₁ Label) (lts₂ : LTS State₂ Label) :
                                          lts₁.WeakBisimilarity lts₂ = fun (s₁ : State₁) (s₂ : State₂) => ∃ (r : State₁ → State₂ → Prop), r s₁ s₂ ∧ lts₁.IsSWBisimulation lts₂ r

                                          Weak bisimilarity can also be characterized through sw-bisimulations.

                                          theorem Cslib.LTS.HomWeakBisimilarity.refl {Label : Type u_3} {State : Type u_4} [HasTau Label] {lts : LTS State Label} (s : State) :

                                          Homogeneous weak bisimilarity is reflexive.

                                          theorem Cslib.LTS.IsWeakBisimulation.inv {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (r : State₁ → State₂ → Prop) (h : lts₁.IsWeakBisimulation lts₂ r) :
                                          lts₂.IsWeakBisimulation lts₁ (flip r)

                                          The inverse of a weak bisimulation is a weak bisimulation.

                                          theorem Cslib.LTS.WeakBisimilarity.symm {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {s₁ : State₁} {s₂ : State₂} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} (h : lts₁.WeakBisimilarity lts₂ s₁ s₂) :
                                          lts₂.WeakBisimilarity lts₁ s₂ s₁

                                          Weak bisimilarity is symmetric.

                                          theorem Cslib.LTS.IsWeakBisimulation.comp {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {State₃ : Type u_4} {r1 : State₁ → State₂ → Prop} {r2 : State₂ → State₃ → Prop} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {lts₃ : LTS State₃ Label} (h1 : lts₁.IsWeakBisimulation lts₂ r1) (h2 : lts₂.IsWeakBisimulation lts₃ r2) :
                                          lts₁.IsWeakBisimulation lts₃ (Relation.Comp r1 r2)

                                          The composition of two weak bisimulations is a weak bisimulation.

                                          theorem Cslib.LTS.IsSWBisimulation.comp {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {State₃ : Type u_4} {r1 : State₁ → State₂ → Prop} {r2 : State₂ → State₃ → Prop} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {lts₃ : LTS State₃ Label} (h1 : lts₁.IsSWBisimulation lts₂ r1) (h2 : lts₂.IsSWBisimulation lts₃ r2) :
                                          lts₁.IsSWBisimulation lts₃ (Relation.Comp r1 r2)

                                          The composition of two sw-bisimulations is an sw-bisimulation.

                                          theorem Cslib.LTS.WeakBisimilarity.trans {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} {State₃ : Type u_4} {s₁ : State₁} {s₂ : State₂} {s₃ : State₃} [HasTau Label] {lts₁ : LTS State₁ Label} {lts₂ : LTS State₂ Label} {lts₃ : LTS State₃ Label} (h1 : lts₁.WeakBisimilarity lts₂ s₁ s₂) (h2 : lts₂.WeakBisimilarity lts₃ s₂ s₃) :
                                          lts₁.WeakBisimilarity lts₃ s₁ s₃

                                          Weak bisimilarity is transitive.

                                          theorem Cslib.LTS.HomWeakBisimilarity.eqv {Label : Type u_3} {State : Type u_4} [HasTau Label] {lts : LTS State Label} :

                                          Homogeneous weak bisimilarity is an equivalence relation.

                                          Reindex an LTS by an equivalence between two state types #

                                          def Cslib.LTS.reindex {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (e : State₁ ≃ State₂) :
                                          LTS State₂ Label

                                          Reindex an LTS by an equivalence between two state types.

                                          Equations
                                          • lts₁.reindex e = { Tr := fun (s₂ : State₂) (a : Label) (t₂ : State₂) => lts₁.Tr (e.symm s₂) a (e.symm t₂) }
                                          Instances For
                                            theorem Cslib.LTS.reindex.tr {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (e : State₁ ≃ State₂) (s₁ t₁ : State₁) (μ : Label) :
                                            (lts₁.reindex e).Tr (e s₁) μ (e t₁) ↔ lts₁.Tr s₁ μ t₁
                                            theorem Cslib.LTS.reindex.isBisimulation {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (e : State₁ ≃ State₂) :
                                            lts₁.IsBisimulation (lts₁.reindex e) fun (s : State₁) (s' : State₂) => s' = e s
                                            theorem Cslib.LTS.reindex.bisim_trace {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (e : State₁ ≃ State₂) (s₁ t₁ : State₁) (μs : List Label) :
                                            lts₁.MTr s₁ μs t₁ → (lts₁.reindex e).MTr (e s₁) μs (e t₁)
                                            theorem Cslib.LTS.reindex.bisim_trace_iff {State₁ : Type u_1} {State₂ : Type u_2} {Label : Type u_3} (lts₁ : LTS State₁ Label) (e : State₁ ≃ State₂) (s₁ t₁ : State₁) (μs : List Label) :
                                            lts₁.MTr s₁ μs t₁ ↔ (lts₁.reindex e).MTr (e s₁) μs (e t₁)