Normal forms retaining split-variable resolutions
Lax369799.FiniteResolutionNormalForms · concepts/Lax369799/FiniteResolutionNormalForms.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite disjoint family of initial and planted root resolutions can preserve every bounded profile of a presentation. Each component is a whole deterministic system; its internal branching is retained.
Concept map
Evidence
This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.
1 bounded_normal_form proven
2 contextual_normal_form proven
Lean source view on GitHub
| 1 | import Lax369799.ResolutionFamilies |
| 2 | import Lax369799.BoundedProfileRefinement |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Normal forms retaining split-variable resolutions |
| 7 | type: theorem |
| 8 | --- |
| 9 | A finite disjoint family of initial and planted root resolutions can |
| 10 | preserve every bounded profile of a presentation. Each component is a |
| 11 | whole deterministic system; its internal branching is retained. |
| 12 | -/ |
| 13 | namespace Lax369799.FiniteResolutionNormalForms |
| 14 | open RankedSystems Morphisms FinitePresentations FiniteProfiles |
| 15 | |
| 16 | structure Component {A : RankedSet} {n : ℕ} (S : SetSystem A n) where |
| 17 | system : System A n |
| 18 | rooted : Bool |
| 19 | resolves : DirectResolution (if rooted then RankedSystems.uproot S else S) system |
| 20 | |
| 21 | def familyGraph {A : RankedSet} {n : ℕ} {I : Type} {S : SetSystem A n} |
| 22 | (c : I → Component S) : Presentation A n ((i : I) × (c i).system.val.Vertex) where |
| 23 | label := fun v => ((c v.1).system.val.graph.label v.2) |
| 24 | initial := fun v => (c v.1).rooted = false ∧ v.2 ∈ (c v.1).system.val.graph.initial |
| 25 | root := fun v => (c v.1).rooted = true ∧ v.2 ∈ (c v.1).system.val.graph.initial |
| 26 | edge := fun v d t => ∃ s, (c v.1).system.val.graph.edge v.2 d s ∧ |
| 27 | t = Sum.map (Sigma.mk v.1) id s |
| 28 | direction_valid := by rintro v d t ⟨s, hs, _⟩; exact (c v.1).system.val.graph.direction_valid v.2 d s hs |
| 29 | |
| 30 | noncomputable def family {A : RankedSet} {n : ℕ} {I : Type} [Fintype I] |
| 31 | {S : SetSystem A n} (c : I → Component S) : FiniteSystem A n := enumerate (familyGraph c) |
| 32 | |
| 33 | axiom bounded_normal_form {A B : RankedSet} (hB : RankwiseFinite B) (bound : ℕ) |
| 34 | (ρ : ∀ n, System A n → B n) {n : ℕ} (S : FiniteSystem A n) : |
| 35 | ∃ (k : ℕ) (c : Fin k → Component (trim S.graph)), |
| 36 | BoundedProfileEquivalent bound ρ S (family c) |
| 37 | |
| 38 | axiom contextual_normal_form {A B : RankedSet} (E : Algebras.Algebra B) |
| 39 | (hE : Algebras.UnfoldInvariant E) (hB : RankwiseFinite B) |
| 40 | (η : RankedMap A B) (F : Set (B 0)) (L : Algebras.Language A) |
| 41 | (hL : Algebras.Recognizes E η F L) {n : ℕ} (S : FiniteSystem A n) : |
| 42 | ∃ (k : ℕ) (c : Fin k → Component (trim S.graph)), |
| 43 | FiniteContextualOrder.quotientMap (FiniteAcceptance.Accepting L) n S = |
| 44 | FiniteContextualOrder.quotientMap (FiniteAcceptance.Accepting L) n (family c) |
| 45 | |
| 46 | end Lax369799.FiniteResolutionNormalForms |
| 47 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments