Arbitrary transition systems and bisimulations
Lax369799.UnrestrictedTransitionSystems · concepts/Lax369799/UnrestrictedTransitionSystems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A pointed transition system may have an arbitrary state space. The usual back-and-forth definition of bisimulation imposes no finiteness or reachability assumption. Finite transition systems embed by retaining their vertices, initial point, edges, and proposition valuations.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.TransitionSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Arbitrary transition systems and bisimulations |
| 6 | type: definition |
| 7 | --- |
| 8 | A pointed transition system may have an arbitrary state space. The usual |
| 9 | back-and-forth definition of bisimulation imposes no finiteness or |
| 10 | reachability assumption. Finite transition systems embed by retaining |
| 11 | their vertices, initial point, edges, and proposition valuations. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.UnrestrictedTransitionSystems |
| 15 | |
| 16 | structure TransitionSystem (P : Type) where |
| 17 | Vertex : Type |
| 18 | initial : Vertex |
| 19 | edge : Vertex → Vertex → Prop |
| 20 | valuation : Vertex → Set P |
| 21 | |
| 22 | def ofFinite {P : Type} (S : TransitionSystems.TransitionSystem P) : TransitionSystem P := |
| 23 | ⟨S.Vertex,S.initial,S.edge,S.valuation⟩ |
| 24 | |
| 25 | def Bisimulation {P : Type} (S T : TransitionSystem P) |
| 26 | (R : S.Vertex → T.Vertex → Prop) : Prop := |
| 27 | R S.initial T.initial ∧ ∀ v w, R v w → |
| 28 | S.valuation v = T.valuation w ∧ |
| 29 | (∀ v', S.edge v v' → ∃ w', T.edge w w' ∧ R v' w') ∧ |
| 30 | (∀ w', T.edge w w' → ∃ v', S.edge v v' ∧ R v' w') |
| 31 | |
| 32 | def Bisimilar {P : Type} (S T : TransitionSystem P) : Prop := |
| 33 | ∃ R, Bisimulation S T R |
| 34 | |
| 35 | def BisimulationInvariant {P : Type} (L : Set (TransitionSystem P)) : Prop := |
| 36 | ∀ S T, Bisimilar S T → (S ∈ L ↔ T ∈ L) |
| 37 | |
| 38 | end Lax369799.UnrestrictedTransitionSystems |
| 39 | |
| 40 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments