Ranked encodings of transition systems
Lax369799.TransitionEncoding · concepts/Lax369799/TransitionEncoding.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The transition alphabet has a copy of every proposition valuation in every rank. Decoding a closed system forgets the order and multiplicity of its outgoing edges. Ranked bisimilarity is generated by unfold-equivalence and having isomorphic decodings. Section 6.1 proves that this is exactly usual bisimilarity of the decoded transition systems.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.TransitionSystems |
| 2 | import Lax369799.Morphisms |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Ranked encodings of transition systems |
| 7 | type: definition |
| 8 | --- |
| 9 | The transition alphabet has a copy of every proposition valuation in every |
| 10 | rank. Decoding a closed system forgets the order and multiplicity of its |
| 11 | outgoing edges. Ranked bisimilarity is generated by unfold-equivalence and |
| 12 | having isomorphic decodings. Section 6.1 proves that this is exactly usual |
| 13 | bisimilarity of the decoded transition systems. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.TransitionEncoding |
| 17 | open RankedSystems Morphisms TransitionSystems |
| 18 | |
| 19 | abbrev TransitionAlphabet (P : Type) : RankedSet := fun _ => Set P |
| 20 | |
| 21 | noncomputable def decode {P : Type} (S : System (TransitionAlphabet P) 0) : |
| 22 | TransitionSystem P where |
| 23 | size := S.val.size |
| 24 | initial := Classical.choose S.property.1 |
| 25 | edge := fun v w => ∃ d, S.val.graph.edge v d (.inl w) |
| 26 | valuation := fun v => (S.val.graph.label v).2 |
| 27 | reachable := by |
| 28 | intro v |
| 29 | obtain ⟨r, hr, hp⟩ := S.val.reachable v |
| 30 | have hi := Classical.choose_spec S.property.1 |
| 31 | rcases hr with hr | hr |
| 32 | · rw [hi] at hr |
| 33 | have he : r = Classical.choose S.property.1 := hr |
| 34 | subst r |
| 35 | exact hp |
| 36 | · rw [S.property.2.1] at hr |
| 37 | exact False.elim hr |
| 38 | |
| 39 | def Isomorphic {P : Type} (S T : TransitionSystem P) : Prop := |
| 40 | ∃ e : S.Vertex ≃ T.Vertex, e S.initial = T.initial ∧ |
| 41 | (∀ v, S.valuation v = T.valuation (e v)) ∧ |
| 42 | ∀ v w, S.edge v w ↔ T.edge (e v) (e w) |
| 43 | |
| 44 | def RankedBisimilar {P : Type} (S T : System (TransitionAlphabet P) 0) : Prop := |
| 45 | Relation.EqvGen (fun U V => UnfoldEquivalent U.val V.val ∨ |
| 46 | Isomorphic (decode U) (decode V)) S T |
| 47 | |
| 48 | end Lax369799.TransitionEncoding |
| 49 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments