Resolutions and bounded profiles
Lax369799.Resolutions · concepts/Lax369799/Resolutions.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A resolution consists of a system and a map from its variables to those of the target set-system, such that the renamed system maps into the target. A flatten-resolution resolves both the outer pattern and its labels, keeping track of a separate variable map at each vertex (Section 2.9).
For a recognising evaluation, a profile records the values and variable maps of resolutions. A map is small when each fibre has at most elements, accounting for closed continuations, unary continuations, and the immediate exit. This is the bound b_A in the revised Section 4.3. Small profiles and small root profiles are the finite summaries used there.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.Algebras |
| 2 | import Mathlib.SetTheory.Cardinal.Finite |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Resolutions and bounded profiles |
| 7 | type: definition |
| 8 | --- |
| 9 | A resolution consists of a system and a map from its variables to those of |
| 10 | the target set-system, such that the renamed system maps into the target. |
| 11 | A flatten-resolution resolves both the outer pattern and its labels, |
| 12 | keeping track of a separate variable map at each vertex (Section 2.9). |
| 13 | |
| 14 | For a recognising evaluation, a profile records the values and variable |
| 15 | maps of resolutions. A map is small when each fibre has at most |
| 16 | `|B₀| + |B₁| + 1` elements, accounting for closed continuations, unary |
| 17 | continuations, and the immediate exit. This is the bound b_A in the |
| 18 | revised Section 4.3. Small profiles and small root profiles are the finite |
| 19 | summaries used there. |
| 20 | -/ |
| 21 | |
| 22 | namespace Lax369799.Resolutions |
| 23 | open RankedSystems Morphisms Flattening Algebras |
| 24 | |
| 25 | def rename {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 26 | (S : SetSystem A m) : SetSystem A n where |
| 27 | size := S.size |
| 28 | graph := { |
| 29 | label := S.graph.label |
| 30 | initial := S.graph.initial |
| 31 | root := S.graph.root |
| 32 | edge := fun v d t => ∃ s, S.graph.edge v d s ∧ t = Sum.map id σ s |
| 33 | direction_valid := by |
| 34 | rintro v d t ⟨s, hs, _⟩ |
| 35 | exact S.graph.direction_valid v d s hs } |
| 36 | reachable := by |
| 37 | intro v |
| 38 | obtain ⟨r, hr, hp⟩ := S.reachable v |
| 39 | refine ⟨r, hr, Relation.ReflTransGen.mono ?_ r v hp⟩ |
| 40 | rintro a b ⟨d, hd⟩ |
| 41 | exact ⟨d, .inl b, hd, rfl⟩ |
| 42 | |
| 43 | def IsResolution {A : RankedSet} {m n : ℕ} (S : SetSystem A n) |
| 44 | (T : System A m) (σ : Fin m → Fin n) : Prop := |
| 45 | Nonempty (Morphism (rename σ T.val) S) |
| 46 | |
| 47 | structure FlattenResolution {A : RankedSet} {n : ℕ} |
| 48 | (S : SetSystem (SetSystem A) n) (T : System (System A) n) where |
| 49 | vertex : T.val.Vertex → S.Vertex |
| 50 | variableMap : ∀ v, Fin (T.val.graph.label v).1 → Fin (S.graph.label (vertex v)).1 |
| 51 | initial : ∀ v, v ∈ T.val.graph.initial → vertex v ∈ S.graph.initial |
| 52 | resolves : ∀ v, IsResolution (Inner S (vertex v)) (T.val.graph.label v).2 (variableMap v) |
| 53 | transition : ∀ v (i : Fin (T.val.graph.label v).1) w, |
| 54 | T.val.graph.edge v i.val (.inl w) → S.graph.edge (vertex v) (variableMap v i).val (.inl (vertex w)) |
| 55 | exit : ∀ v (i : Fin (T.val.graph.label v).1) j, |
| 56 | T.val.graph.edge v i.val (.inr j) → S.graph.edge (vertex v) (variableMap v i).val (.inr j) |
| 57 | |
| 58 | abbrev ProfileEntry (B : RankedSet) (n : ℕ) := (m : ℕ) × B m × (Fin m → Fin n) |
| 59 | |
| 60 | noncomputable def SmallBound (B : RankedSet) : ℕ := Nat.card (B 0) + Nat.card (B 1) + 1 |
| 61 | |
| 62 | def SmallMap (B : RankedSet) {m n : ℕ} (σ : Fin m → Fin n) : Prop := |
| 63 | ∀ j, Nat.card {i // σ i = j} ≤ SmallBound B |
| 64 | |
| 65 | def Profile {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ} |
| 66 | (S : SetSystem A n) : Set (ProfileEntry B n) := |
| 67 | {e | ∃ T : System A e.1, IsResolution S T e.2.2 ∧ ρ e.1 T = e.2.1} |
| 68 | |
| 69 | def SmallProfile {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ} |
| 70 | (S : SetSystem A n) : Set (ProfileEntry B n) := |
| 71 | {e | e ∈ Profile ρ S ∧ SmallMap B e.2.2} |
| 72 | |
| 73 | def ProfileEquivalent {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ} |
| 74 | (S T : SetSystem A n) : Prop := |
| 75 | Profile ρ S = Profile ρ T ∧ Profile ρ (uproot S) = Profile ρ (uproot T) |
| 76 | |
| 77 | def SmallProfileEquivalent {A B : RankedSet} (ρ : ∀ n, System A n → B n) {n : ℕ} |
| 78 | (S T : SetSystem A n) : Prop := |
| 79 | SmallProfile ρ S = SmallProfile ρ T ∧ SmallProfile ρ (uproot S) = SmallProfile ρ (uproot T) |
| 80 | |
| 81 | end Lax369799.Resolutions |
| 82 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments