Finite transition systems and bisimulation
Lax369799.TransitionSystems · concepts/Lax369799/TransitionSystems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Lean source view on GitHub
| 1 | import Lax369799.RankedSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Finite transition systems and bisimulation |
| 6 | type: definition |
| 7 | --- |
| 8 | A finite transition system is a finite directed graph with an initial vertex |
| 9 | and a valuation of proposition letters at each vertex. All vertices are |
| 10 | reachable from the initial vertex. A bisimulation relates the initial |
| 11 | vertices, preserves valuations, and matches successors in both directions. |
| 12 | This is the usual bisimulation of Section 6.1, without an ordering or |
| 13 | multiplicity on the successors. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.TransitionSystems |
| 17 | |
| 18 | structure 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 | |
| 25 | abbrev TransitionSystem.Vertex {P : Type} (S : TransitionSystem P) := Fin S.size |
| 26 | |
| 27 | def 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 | |
| 34 | def Bisimilar {P : Type} (S T : TransitionSystem P) : Prop := |
| 35 | ∃ R, Bisimulation S T R |
| 36 | |
| 37 | def BisimulationInvariant {P : Type} (L : Set (TransitionSystem P)) : Prop := |
| 38 | ∀ S T, Bisimilar S T → (S ∈ L ↔ T ∈ L) |
| 39 | |
| 40 | end Lax369799.TransitionSystems |
| 41 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments