Yield-syntactic order and quotient
Lax369799.SyntacticOrder · concepts/Lax369799/SyntacticOrder.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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. records a set-algebra structure on the resulting quotient whose evaluation commutes with the quotient map. See Section 4.2.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.SetAlgebras |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Yield-syntactic order and quotient |
| 6 | type: definition |
| 7 | --- |
| 8 | A closed set-system is accepting when all its initial and root yields |
| 9 | belong to the language or its planted copy. The yield-syntactic preorder |
| 10 | compares these acceptance tests in every closed context with one hole. |
| 11 | Mutual comparison defines the syntactic equivalence. `SyntacticAlgebra` |
| 12 | records a set-algebra structure on the resulting quotient whose evaluation |
| 13 | commutes with the quotient map. See Section 4.2. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.SyntacticOrder |
| 17 | open RankedSystems Morphisms Flattening Algebras SetAlgebras |
| 18 | |
| 19 | def 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 | |
| 22 | def 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 | |
| 26 | def SyntacticEquivalent {A : RankedSet} (L : Language A) {n : ℕ} |
| 27 | (S T : SetSystem A n) : Prop := SyntacticBelow L S T ∧ SyntacticBelow L T S |
| 28 | |
| 29 | abbrev SyntacticCarrier {A : RankedSet} (L : Language A) : RankedSet := |
| 30 | fun n => Quot (@SyntacticEquivalent A L n) |
| 31 | |
| 32 | def syntacticMap {A : RankedSet} (L : Language A) : |
| 33 | RankedMap (SetSystem A) (SyntacticCarrier L) := fun _ => Quot.mk _ |
| 34 | |
| 35 | structure 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 | |
| 40 | end Lax369799.SyntacticOrder |
| 41 |
Builds on
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments