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

Ranked encodings of transition systems

Lax369799.TransitionEncoding · concepts/Lax369799/TransitionEncoding.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

    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
    4 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.TransitionSystems
    2import Lax369799.Morphisms
    3
    4/-!
    5---
    6title: Ranked encodings of transition systems
    7type: definition
    8---
    9The transition alphabet has a copy of every proposition valuation in every
    10rank. Decoding a closed system forgets the order and multiplicity of its
    11outgoing edges. Ranked bisimilarity is generated by unfold-equivalence and
    12having isomorphic decodings. Section 6.1 proves that this is exactly usual
    13bisimilarity of the decoded transition systems.
    14-/
    15
    16namespace Lax369799.TransitionEncoding
    17open RankedSystems Morphisms TransitionSystems
    18
    19abbrev TransitionAlphabet (P : Type) : RankedSet := fun _ => Set P
    20
    21noncomputable 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
    39def 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
    44def 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
    48end Lax369799.TransitionEncoding
    49

    Discussion

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

    Loading discussion…