Quotients of graphs by vertex bisimilarity
Lax369799.BisimulationQuotient · concepts/Lax369799/BisimulationQuotient.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Vertex bisimilarity compares labeled graphs without selecting an initial vertex. On one graph it is an equivalence relation. The quotient graph has a functional bisimulation from the original graph, with successor lifting. These quotients support the converse ranked encoding theorem.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.TransitionSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Quotients of graphs by vertex bisimilarity |
| 6 | type: theorem |
| 7 | --- |
| 8 | Vertex bisimilarity compares labeled graphs without selecting an initial |
| 9 | vertex. On one graph it is an equivalence relation. The quotient graph |
| 10 | has a functional bisimulation from the original graph, with successor |
| 11 | lifting. These quotients support the converse ranked encoding theorem. |
| 12 | -/ |
| 13 | namespace Lax369799.BisimulationQuotient |
| 14 | |
| 15 | structure Graph (P V : Type) where |
| 16 | edge : V → V → Prop |
| 17 | valuation : V → Set P |
| 18 | |
| 19 | structure BisimulationMap {P V W : Type} (G : Graph P V) (H : Graph P W) where |
| 20 | toFun : V → W |
| 21 | valuation : ∀ v, G.valuation v = H.valuation (toFun v) |
| 22 | forward : ∀ v w, G.edge v w → H.edge (toFun v) (toFun w) |
| 23 | backward : ∀ v w, H.edge (toFun v) w → ∃ v', G.edge v v' ∧ toFun v' = w |
| 24 | |
| 25 | def IsBisimulation {P V W : Type} (G : Graph P V) (H : Graph P W) |
| 26 | (R : V → W → Prop) : Prop := |
| 27 | ∀ v w, R v w → G.valuation v = H.valuation w ∧ |
| 28 | (∀ v', G.edge v v' → ∃ w', H.edge w w' ∧ R v' w') ∧ |
| 29 | (∀ w', H.edge w w' → ∃ v', G.edge v v' ∧ R v' w') |
| 30 | |
| 31 | def Related {P V W : Type} (G : Graph P V) (H : Graph P W) (v : V) (w : W) : Prop := |
| 32 | ∃ R, IsBisimulation G H R ∧ R v w |
| 33 | |
| 34 | abbrev Carrier {P V : Type} (G : Graph P V) := Quot (Related G G) |
| 35 | |
| 36 | def quotient {P V : Type} (G : Graph P V) : Graph P (Carrier G) where |
| 37 | valuation := Quot.lift G.valuation (by |
| 38 | rintro v w ⟨R, hR, h⟩ |
| 39 | exact (hR v w h).1) |
| 40 | edge := fun q r => ∃ v w, Quot.mk (Related G G) v = q ∧ |
| 41 | Quot.mk (Related G G) w = r ∧ G.edge v w |
| 42 | |
| 43 | axiom related_equivalence {P V : Type} (G : Graph P V) : Equivalence (Related G G) |
| 44 | |
| 45 | axiom quotient_projection {P V : Type} (G : Graph P V) : |
| 46 | ∃ f : BisimulationMap G (quotient G), f.toFun = Quot.mk (Related G G) |
| 47 | |
| 48 | def ofSystem {P : Type} (S : TransitionSystems.TransitionSystem P) : Graph P S.Vertex := |
| 49 | ⟨S.edge, S.valuation⟩ |
| 50 | |
| 51 | structure SystemMap {P : Type} (S T : TransitionSystems.TransitionSystem P) |
| 52 | extends BisimulationMap (ofSystem S) (ofSystem T) where |
| 53 | initial : toFun S.initial = T.initial |
| 54 | |
| 55 | axiom common_quotient {P : Type} (S T : TransitionSystems.TransitionSystem P) |
| 56 | (h : TransitionSystems.Bisimilar S T) : |
| 57 | ∃ U : TransitionSystems.TransitionSystem P, Nonempty (SystemMap S U) ∧ Nonempty (SystemMap T U) |
| 58 | |
| 59 | end Lax369799.BisimulationQuotient |
| 60 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments