Yield acceptance of finite presentations
Lax369799.FiniteAcceptance · concepts/Lax369799/FiniteAcceptance.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Acceptance tests the yields starting at initial or root vertices. For an ordinary finite presentation this is computed on its reachable restriction. This final observation does not prune intermediate substitution patterns. The resulting isomorphism-invariant property has a contextual quotient algebra for unpruned substitution.
Concept map
Evidence
This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.
1 accepting_empty proven
2 accepting_isomorphic proven
3 accepting_sum proven
4 accepting_system proven
5 syntactic_substitution_algebra proven
Lean source view on GitHub
| 1 | import Lax369799.FiniteSyntacticAlgebra |
| 2 | import Lax369799.SyntacticOrder |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Yield acceptance of finite presentations |
| 7 | type: definition |
| 8 | --- |
| 9 | Acceptance tests the yields starting at initial or root vertices. For an |
| 10 | ordinary finite presentation this is computed on its reachable restriction. |
| 11 | This final observation does not prune intermediate substitution patterns. |
| 12 | The resulting isomorphism-invariant property has a contextual quotient |
| 13 | algebra for unpruned substitution. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.FiniteAcceptance |
| 17 | open RankedSystems (RankedSet) |
| 18 | open FinitePresentations FiniteContextualOrder |
| 19 | |
| 20 | def Accepting {A : RankedSet} (L : Algebras.Language A) (S : FiniteSystem A 0) : Prop := |
| 21 | SyntacticOrder.Accepting L (RankedSystems.trim S.graph) |
| 22 | |
| 23 | axiom accepting_isomorphic {A : RankedSet} (L : Algebras.Language A) : |
| 24 | IsoInvariant (Accepting L) |
| 25 | |
| 26 | axiom syntactic_substitution_algebra {A : RankedSet} (L : Algebras.Language A) : |
| 27 | ∃ E : FiniteSyntacticAlgebra.Algebra (Carrier (Accepting L)), |
| 28 | ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 29 | E.eval n (relabel (quotientMap (Accepting L)) S) = |
| 30 | quotientMap (Accepting L) n (flatten S) |
| 31 | |
| 32 | axiom accepting_sum {A : RankedSet} (L : Algebras.Language A) (S T : FiniteSystem A 0) : |
| 33 | Accepting L (sum S T) ↔ Accepting L S ∧ Accepting L T |
| 34 | |
| 35 | axiom accepting_system {A : RankedSet} (L : Algebras.Language A) |
| 36 | (hL : Algebras.UnfoldInvariantLanguage L) (S : RankedSystems.System A 0) : |
| 37 | Accepting L (ofSetSystem S.val) ↔ S ∈ L |
| 38 | |
| 39 | axiom accepting_empty {A : RankedSet} (L : Algebras.Language A) : |
| 40 | Accepting L (empty A 0) |
| 41 | |
| 42 | end Lax369799.FiniteAcceptance |
| 43 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments