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

Contextual equivalence of deterministic systems

Lax369799.DeterministicSyntacticOrder · concepts/Lax369799/DeterministicSyntacticOrder.lean · lax-369799

proven

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

    Theorem

    Two systems are equivalent when every closed deterministic context gives the same language-membership test. Recognition by a rankwise-finite algebra makes this quotient rankwise finite, without requiring the recognizing algebra itself to be unfolding-invariant. For an unfolding-invariant language, equivalent unfoldings have the same contextual class.

    Concept map
    9 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Lax369799.ContextRelabelling
    2
    3/-!
    4---
    5title: Contextual equivalence of deterministic systems
    6type: theorem
    7---
    8Two systems are equivalent when every closed deterministic context gives
    9the same language-membership test. Recognition by a rankwise-finite algebra
    10makes this quotient rankwise finite, without requiring the recognizing
    11algebra itself to be unfolding-invariant. For an unfolding-invariant
    12language, equivalent unfoldings have the same contextual class.
    13-/
    14namespace Lax369799.DeterministicSyntacticOrder
    15open RankedSystems Flattening Algebras Morphisms
    16
    17def Test {A : RankedSet} (L : Language A) {n : ℕ} (C : Context A n 0) (S : System A n) : Prop :=
    18 ∃ U : System A 0, U.val = plug C.val S.val ∧ U ∈ L
    19
    20def Equivalent {A : RankedSet} (L : Language A) {n : ℕ} (S T : System A n) : Prop :=
    21 ∀ C : Context A n 0, Test L C S ↔ Test L C T
    22
    23abbrev Carrier {A : RankedSet} (L : Language A) : RankedSet := fun n => Quot (@Equivalent A L n)
    24
    25axiom value_refines {A B : RankedSet} (E : Algebra B) (η : RankedMap A B)
    26 (F : Set (B 0)) (L : Language A) (hL : Recognizes E η F L)
    27 {n : ℕ} (S T : System A n)
    28 (h : E.eval n (relabelSystem η S) = E.eval n (relabelSystem η T)) : Equivalent L S T
    29
    30axiom unfold_refines {A : RankedSet} (L : Language A) (hL : UnfoldInvariantLanguage L)
    31 {n : ℕ} (S T : System A n) (h : UnfoldEquivalent S.val T.val) : Equivalent L S T
    32
    33def AcceptingClass {A : RankedSet} (L : Language A) (a : Carrier L 0) : Prop :=
    34 ∃ S : System A 0, Quot.mk _ S = a ∧ S ∈ L
    35
    36axiom closed_membership {A : RankedSet} (L : Language A) (hL : UnfoldInvariantLanguage L)
    37 (S T : System A 0) (h : Equivalent L S T) : S ∈ L ↔ T ∈ L
    38
    39axiom accepting_class {A : RankedSet} (L : Language A) (hL : UnfoldInvariantLanguage L)
    40 (S : System A 0) : AcceptingClass L (Quot.mk _ S) ↔ S ∈ L
    41
    42axiom finite_carrier {A : RankedSet} (L : Language A) (hL : Recognizable L) : RankwiseFinite (Carrier L)
    43
    44end Lax369799.DeterministicSyntacticOrder
    45
    Show ProofShow ProofShow ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…