While this submission is a draft, it cannot be used by other submissions.

Finite transition systems and bisimulation

Lax369799.TransitionSystems · concepts/Lax369799/TransitionSystems.lean · lax-369799

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A finite transition system is a finite directed graph with an initial vertex and a valuation of proposition letters at each vertex. All vertices are reachable from the initial vertex. A bisimulation relates the initial vertices, preserves valuations, and matches successors in both directions. This is the usual bisimulation of Section 6.1, without an ordering or multiplicity on the successors.

    Concept map
    2 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Lax369799.RankedSystems
    2
    3/-!
    4---
    5title: Finite transition systems and bisimulation
    6type: definition
    7---
    8A finite transition system is a finite directed graph with an initial vertex
    9and a valuation of proposition letters at each vertex. All vertices are
    10reachable from the initial vertex. A bisimulation relates the initial
    11vertices, preserves valuations, and matches successors in both directions.
    12This is the usual bisimulation of Section 6.1, without an ordering or
    13multiplicity on the successors.
    14-/
    15
    16namespace Lax369799.TransitionSystems
    17
    18structure TransitionSystem (P : Type) where
    19 size : ℕ
    20 initial : Fin size
    21 edge : Fin size → Fin size → Prop
    22 valuation : Fin size → Set P
    23 reachable : ∀ v, Relation.ReflTransGen edge initial v
    24
    25abbrev TransitionSystem.Vertex {P : Type} (S : TransitionSystem P) := Fin S.size
    26
    27def Bisimulation {P : Type} (S T : TransitionSystem P)
    28 (R : S.Vertex → T.Vertex → Prop) : Prop :=
    29 R S.initial T.initial ∧ ∀ v w, R v w →
    30 S.valuation v = T.valuation w ∧
    31 (∀ v', S.edge v v' → ∃ w', T.edge w w' ∧ R v' w') ∧
    32 (∀ w', T.edge w w' → ∃ v', S.edge v v' ∧ R v' w')
    33
    34def Bisimilar {P : Type} (S T : TransitionSystem P) : Prop :=
    35 ∃ R, Bisimulation S T R
    36
    37def BisimulationInvariant {P : Type} (L : Set (TransitionSystem P)) : Prop :=
    38 ∀ S T, Bisimilar S T → (S ∈ L ↔ T ∈ L)
    39
    40end Lax369799.TransitionSystems
    41

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…