Acceptance and the syntactic preorder
Lax369799.AcceptanceTheorems · concepts/Lax369799/AcceptanceTheorems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Acceptance is invariant under unfolding. On deterministic systems it agrees with membership in the original unfold-invariant language. The syntactic preorder reverses morphisms and preserves acceptance on closed systems, so acceptance descends to the syntactic quotient.
Concept map
Evidence
This concept declares 7 statements. Each proof establishes one of them relative to its assumptions.
1 accepting_plant proven
2 accepting_sum proven
3 accepting_system proven
4 accepting_unfold proven
5 syntactic_acceptance proven
6 syntactic_morphism proven
7 yield_sum proven
Lean source view on GitHub
| 1 | import Lax369799.SyntacticOrder |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Acceptance and the syntactic preorder |
| 6 | type: theorem |
| 7 | --- |
| 8 | Acceptance is invariant under unfolding. On deterministic systems it |
| 9 | agrees with membership in the original unfold-invariant language. The |
| 10 | syntactic preorder reverses morphisms and preserves acceptance on closed |
| 11 | systems, so acceptance descends to the syntactic quotient. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.AcceptanceTheorems |
| 15 | open RankedSystems Morphisms Algebras SyntacticOrder |
| 16 | |
| 17 | axiom yield_sum {A : RankedSet} {n : ℕ} (S T U : SetSystem A n) : |
| 18 | Yield (sum S T) U ↔ Yield S U ∨ Yield T U |
| 19 | |
| 20 | axiom accepting_sum {A : RankedSet} (L : Language A) (S T : SetSystem A 0) : |
| 21 | Accepting L (sum S T) ↔ Accepting L S ∧ Accepting L T |
| 22 | |
| 23 | axiom accepting_system {A : RankedSet} (L : Language A) |
| 24 | (hL : UnfoldInvariantLanguage L) (S : System A 0) : |
| 25 | Accepting L S.val ↔ S ∈ L |
| 26 | |
| 27 | axiom accepting_unfold {A : RankedSet} (L : Language A) |
| 28 | (S T : SetSystem A 0) (h : UnfoldEquivalent S T) : |
| 29 | Accepting L S ↔ Accepting L T |
| 30 | |
| 31 | axiom syntactic_morphism {A : RankedSet} (L : Language A) {n : ℕ} |
| 32 | {S T : SetSystem A n} (f : Morphism S T) : SyntacticBelow L T S |
| 33 | |
| 34 | axiom syntactic_acceptance {A : RankedSet} (L : Language A) |
| 35 | {S T : SetSystem A 0} (h : SyntacticBelow L S T) : |
| 36 | Accepting L S → Accepting L T |
| 37 | |
| 38 | axiom accepting_plant {A : RankedSet} (L : Language A) (S : SetSystem A 0) : |
| 39 | Accepting L (plant S) ↔ Accepting L S |
| 40 | |
| 41 | end Lax369799.AcceptanceTheorems |
| 42 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments