Context decomposition without pruning
Lax369799.FiniteDecomposition · concepts/Lax369799/FiniteDecomposition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Retain all vertices in the unary pieces and in their recomposition. The projection covers every original vertex, including unreachable vertices, and restores the hole's initial flag, root flag, and self-loops.
Concept map
Evidence
This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.
1 decomposition_cover proven
2 decomposition_evaluation proven
3 piece_has_no_hole proven
4 recompose_one_hole proven
Lean source view on GitHub
| 1 | import Lax369799.FiniteContexts |
| 2 | import Lax369799.FiniteOrderedAlgebra |
| 3 | import Lax369799.ContextDecomposition |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Context decomposition without pruning |
| 8 | type: theorem |
| 9 | --- |
| 10 | Retain all vertices in the unary pieces and in their recomposition. The |
| 11 | projection covers every original vertex, including unreachable vertices, |
| 12 | and restores the hole's initial flag, root flag, and self-loops. |
| 13 | -/ |
| 14 | namespace Lax369799.FiniteDecomposition |
| 15 | open RankedSystems (RankedSet Presentation) |
| 16 | open Flattening (WithHole IsHole) |
| 17 | open FinitePresentations FiniteContexts |
| 18 | open ContextDecomposition (Boundary CopyVertex recomposePresentation) |
| 19 | |
| 20 | noncomputable def holeVertex {A : RankedSet} {k : ℕ} (C : Context A k 0) : |
| 21 | C.system.Vertex := Classical.choose C.one_hole |
| 22 | |
| 23 | abbrev BodyVertex {A : RankedSet} {k : ℕ} (C : Context A k 0) := |
| 24 | {v : C.system.Vertex // v ≠ holeVertex C} |
| 25 | |
| 26 | noncomputable def boundary {A : RankedSet} {k : ℕ} (C : Context A k 0) : Boundary k where |
| 27 | initial := holeVertex C ∈ C.system.graph.initial |
| 28 | root := holeVertex C ∈ C.system.graph.root |
| 29 | loops := {d | C.system.graph.edge (holeVertex C) d.val (.inl (holeVertex C))} |
| 30 | |
| 31 | noncomputable def piece {A : RankedSet} {k : ℕ} (C : Context A k 0) |
| 32 | (i : Fin (k + 1)) : Presentation (WithHole A k) 1 (BodyVertex C) where |
| 33 | label := fun v => C.system.graph.label v.val |
| 34 | initial := fun v => (i = 0 ∧ v.val ∈ C.system.graph.initial) ∨ |
| 35 | ∃ d : Fin k, i = d.succ ∧ C.system.graph.edge (holeVertex C) d.val (.inl v.val) |
| 36 | root := fun v => v.val ∈ C.system.graph.root |
| 37 | edge := fun v d t => match t with |
| 38 | | .inl w => C.system.graph.edge v.val d (.inl w.val) |
| 39 | | .inr _ => C.system.graph.edge v.val d (.inl (holeVertex C)) |
| 40 | direction_valid := by |
| 41 | intro v d t ht |
| 42 | cases t with |
| 43 | | inl w => exact C.system.graph.direction_valid v.val d _ ht |
| 44 | | inr i => exact C.system.graph.direction_valid v.val d _ ht |
| 45 | |
| 46 | noncomputable def recompose {A : RankedSet} {k : ℕ} (C : Context A k 0) : |
| 47 | FiniteSystem (WithHole A k) 0 := by |
| 48 | classical |
| 49 | exact enumerate (recomposePresentation (boundary C) (piece C)) |
| 50 | |
| 51 | axiom piece_has_no_hole {A : RankedSet} {k : ℕ} (C : Context A k 0) |
| 52 | (i : Fin (k + 1)) (v : BodyVertex C) : ¬ IsHole ((piece C i).label v) |
| 53 | |
| 54 | axiom decomposition_cover {A : RankedSet} {k : ℕ} (C : Context A k 0) : |
| 55 | ∃ f : PresentationCovers.Cover (recompose C).graph C.system.graph, Function.Surjective f.toFun |
| 56 | |
| 57 | axiom recompose_one_hole {A : RankedSet} {k : ℕ} (C : Context A k 0) : |
| 58 | ∃! v, IsHole ((recompose C).graph.label v) |
| 59 | |
| 60 | axiom decomposition_evaluation {A : RankedSet} (L : Algebras.Language A) |
| 61 | (E : FiniteSyntacticAlgebra.Algebra (FiniteContextualOrder.Carrier (FiniteAcceptance.Accepting L))) |
| 62 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 63 | E.eval n (relabel (FiniteContextualOrder.quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 64 | FiniteContextualOrder.quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 65 | {k : ℕ} (C : Context (FiniteContextualOrder.Carrier (FiniteAcceptance.Accepting L)) k 0) : |
| 66 | ∃ D : Context (FiniteContextualOrder.Carrier (FiniteAcceptance.Accepting L)) k 0, |
| 67 | D.system = recompose C ∧ ∀ a, |
| 68 | E.eval 0 (plug D (atomic a)) = E.eval 0 (plug C (atomic a)) |
| 69 | |
| 70 | end Lax369799.FiniteDecomposition |
| 71 |
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