Flattening and contexts
Lax369799.Flattening · concepts/Lax369799/Flattening.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Flattening substitutes a finite set-system at each vertex of a pattern. Inner transition edges are retained; an inner variable edge is connected according to the corresponding direction in the pattern. Inner roots remain roots, and inner initial vertices become roots when the outer vertex is a root. Unreachable vertices are removed. A context has exactly one vertex labelled by a hole of the prescribed rank. See Sections 2.6 and 2.8.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.RankedSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Flattening and contexts |
| 6 | type: definition |
| 7 | --- |
| 8 | Flattening substitutes a finite set-system at each vertex of a pattern. |
| 9 | Inner transition edges are retained; an inner variable edge is connected |
| 10 | according to the corresponding direction in the pattern. Inner roots remain |
| 11 | roots, and inner initial vertices become roots when the outer vertex is a |
| 12 | root. Unreachable vertices are removed. A context has exactly one vertex |
| 13 | labelled by a hole of the prescribed rank. See Sections 2.6 and 2.8. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.Flattening |
| 17 | open RankedSystems |
| 18 | |
| 19 | abbrev Inner {A : RankedSet} {n : ℕ} (S : SetSystem (SetSystem A) n) |
| 20 | (v : S.Vertex) := (S.graph.label v).2 |
| 21 | |
| 22 | noncomputable def flatten {A : RankedSet} {n : ℕ} |
| 23 | (S : SetSystem (SetSystem A) n) : SetSystem A n := |
| 24 | trim (V := (v : S.Vertex) × (Inner S v).Vertex) { |
| 25 | label := fun v => (Inner S v.1).graph.label v.2 |
| 26 | initial := fun v => v.1 ∈ S.graph.initial ∧ v.2 ∈ (Inner S v.1).graph.initial |
| 27 | root := fun v => v.2 ∈ (Inner S v.1).graph.root ∨ |
| 28 | (v.1 ∈ S.graph.root ∧ v.2 ∈ (Inner S v.1).graph.initial) |
| 29 | edge := fun v d t => |
| 30 | (∃ w, (Inner S v.1).graph.edge v.2 d (.inl w) ∧ t = .inl ⟨v.1, w⟩) ∨ |
| 31 | (∃ i : Fin (S.graph.label v.1).1, |
| 32 | (Inner S v.1).graph.edge v.2 d (.inr i) ∧ |
| 33 | ((∃ w : (v : S.Vertex) × (Inner S v).Vertex, |
| 34 | S.graph.edge v.1 i.val (.inl w.1) ∧ |
| 35 | w.2 ∈ (Inner S w.1).graph.initial ∧ t = .inl w) ∨ |
| 36 | (∃ j, S.graph.edge v.1 i.val (.inr j) ∧ t = .inr j))) |
| 37 | direction_valid := by |
| 38 | intro v d t h |
| 39 | rcases h with ⟨w, hw, _⟩ | ⟨i, hi, _⟩ |
| 40 | · exact (Inner S v.1).graph.direction_valid v.2 d _ hw |
| 41 | · exact (Inner S v.1).graph.direction_valid v.2 d _ hi } |
| 42 | |
| 43 | abbrev WithHole (A : RankedSet) (k : ℕ) : RankedSet := fun n => A n ⊕ PLift (k = n) |
| 44 | |
| 45 | def IsHole {A : RankedSet} {k : ℕ} (a : Symbol (WithHole A k)) : Prop := |
| 46 | ∃ h, a.2 = Sum.inr h |
| 47 | |
| 48 | structure SetContext (A : RankedSet) (k n : ℕ) where |
| 49 | system : SetSystem (WithHole A k) n |
| 50 | one_hole : ∃! v, IsHole (system.graph.label v) |
| 51 | |
| 52 | abbrev Context (A : RankedSet) (k n : ℕ) := |
| 53 | {C : SetContext A k n // C.system.Deterministic} |
| 54 | |
| 55 | def substitution {A : RankedSet} {k : ℕ} (S : SetSystem A k) : |
| 56 | RankedMap (WithHole A k) (SetSystem A) := |
| 57 | fun _ a => match a with |
| 58 | | .inl a => atomic a |
| 59 | | .inr ⟨h⟩ => h ▸ S |
| 60 | |
| 61 | noncomputable def plug {A : RankedSet} {k n : ℕ} |
| 62 | (C : SetContext A k n) (S : SetSystem A k) : SetSystem A n := |
| 63 | flatten (relabel (substitution S) C.system) |
| 64 | |
| 65 | /-- The flattening relation avoids making a choice of proof of determinism. -/ |
| 66 | def SystemFlattening {A : RankedSet} {n : ℕ} |
| 67 | (S : System (System A) n) (T : System A n) : Prop := |
| 68 | T.val = flatten (relabel (fun _ U => U.val) S.val) |
| 69 | |
| 70 | end Lax369799.Flattening |
| 71 |
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