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

Yield-syntactic order and quotient

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

    A closed set-system is accepting when all its initial and root yields belong to the language or its planted copy. The yield-syntactic preorder compares these acceptance tests in every closed context with one hole. Mutual comparison defines the syntactic equivalence. SyntacticAlgebraSyntacticAlgebra records a set-algebra structure on the resulting quotient whose evaluation commutes with the quotient map. See Section 4.2.

    Concept map
    6 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.SetAlgebras
    2
    3/-!
    4---
    5title: Yield-syntactic order and quotient
    6type: definition
    7---
    8A closed set-system is accepting when all its initial and root yields
    9belong to the language or its planted copy. The yield-syntactic preorder
    10compares these acceptance tests in every closed context with one hole.
    11Mutual comparison defines the syntactic equivalence. `SyntacticAlgebra`
    12records a set-algebra structure on the resulting quotient whose evaluation
    13commutes with the quotient map. See Section 4.2.
    14-/
    15
    16namespace Lax369799.SyntacticOrder
    17open RankedSystems Morphisms Flattening Algebras SetAlgebras
    18
    19def Accepting {A : RankedSet} (L : Language A) (S : SetSystem A 0) : Prop :=
    20 ∀ T, Yield S T → ∃ U : System A 0, U ∈ L ∧ (T = U.val ∨ T = plant U.val)
    21
    22def SyntacticBelow {A : RankedSet} (L : Language A) {n : ℕ}
    23 (S T : SetSystem A n) : Prop :=
    24 ∀ C : SetContext A n 0, Accepting L (plug C S) → Accepting L (plug C T)
    25
    26def SyntacticEquivalent {A : RankedSet} (L : Language A) {n : ℕ}
    27 (S T : SetSystem A n) : Prop := SyntacticBelow L S T ∧ SyntacticBelow L T S
    28
    29abbrev SyntacticCarrier {A : RankedSet} (L : Language A) : RankedSet :=
    30 fun n => Quot (@SyntacticEquivalent A L n)
    31
    32def syntacticMap {A : RankedSet} (L : Language A) :
    33 RankedMap (SetSystem A) (SyntacticCarrier L) := fun _ => Quot.mk _
    34
    35structure SyntacticAlgebra {A : RankedSet} (L : Language A) where
    36 algebra : SetAlgebra (SyntacticCarrier L)
    37 evaluates : ∀ n (S : SetSystem (SetSystem A) n),
    38 algebra.eval n (relabel (syntacticMap L) S) = syntacticMap L n (flatten S)
    39
    40end Lax369799.SyntacticOrder
    41

    Discussion

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

    Loading discussion…