| 1 | import Lax369799.FiniteExtremal |
| 2 | import Lax369799.DeterministicElements |
| 3 | |
| 12 | namespace Lax369799.SplitExtremal |
| 13 | open RankedSystems (RankedSet) |
| 14 | open FinitePresentations FiniteContextualOrder FiniteSyntacticAlgebra |
| 15 | open ExtremalContexts (Boundary Data) |
| 16 | open FiniteExtremal (IsExtremal Accepts value) |
| 17 | |
| 18 | def component {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 19 | (m : Fin (k + 1) → A 1) (a : A k) (i : Fin k) : FiniteSystem A 1 where |
| 20 | size := k + 2 |
| 21 | graph := { |
| 22 | label := Fin.cases ⟨k, a⟩ (fun j => ⟨1, m j⟩) |
| 23 | initial := {0} |
| 24 | root := fun v => v = (0 : Fin (k + 1)).succ ∨ (v = 0 ∧ B.root) |
| 25 | edge := fun v d t => Fin.cases |
| 26 | ((∃ j : Fin k, d = j.val ∧ t = .inl j.succ.succ) ∨ |
| 27 | (∃ j : Fin k, j ∈ B.loops ∧ d = j.val ∧ t = .inl 0) ∨ |
| 28 | (d = i.val ∧ t = .inr 0)) |
| 29 | (fun _ => d = 0 ∧ t = .inl 0) v |
| 30 | direction_valid := by |
| 31 | intro v d t |
| 32 | refine Fin.cases ?_ (fun j => ?_) v |
| 33 | · rintro (⟨j, rfl, _⟩ | ⟨j, _, rfl, _⟩ | ⟨rfl, _⟩) |
| 34 | · exact j.isLt |
| 35 | · exact j.isLt |
| 36 | · exact i.isLt |
| 37 | · rintro ⟨rfl, _⟩; exact Nat.zero_lt_one } |
| 38 | |
| 39 | def pattern {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 40 | (m : Fin (k + 1) → A 1) (a : A k) : FiniteSystem (FiniteSystem A) k where |
| 41 | size := k |
| 42 | graph := { |
| 43 | label := fun i => ⟨1, component B m a i⟩ |
| 44 | initial := Set.univ |
| 45 | root := ∅ |
| 46 | edge := fun i d t => d = 0 ∧ t = .inr i |
| 47 | direction_valid := by rintro i d t ⟨rfl, _⟩; exact Nat.zero_lt_one } |
| 48 | |
| 49 | noncomputable def delta {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 50 | (m : Fin (k + 1) → A 1) (a : A k) : FiniteSystem A k := flatten (pattern B m a) |
| 51 | |
| 52 | axiom delta_boundary_comparison {A : RankedSet} (L : Algebras.Language A) |
| 53 | (E : Algebra (Carrier (FiniteAcceptance.Accepting L))) |
| 54 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 55 | E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 56 | quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 57 | {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k) |
| 58 | (a : Carrier (FiniteAcceptance.Accepting L) k) |
| 59 | (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) |
| 60 | (hy : Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y) : |
| 61 | (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops |
| 62 | |
| 63 | axiom delta_piece_comparison {A : RankedSet} (L : Algebras.Language A) |
| 64 | (E : Algebra (Carrier (FiniteAcceptance.Accepting L))) |
| 65 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 66 | E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 67 | quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 68 | {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k) |
| 69 | (a : Carrier (FiniteAcceptance.Accepting L) k) |
| 70 | (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) |
| 71 | (hy : Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y) : |
| 72 | ∀ j, ClassBelow (FiniteAcceptance.Accepting L) (x.2 j) (y.2 j) |
| 73 | |
| 74 | axiom delta_below {A : RankedSet} (L : Algebras.Language A) |
| 75 | (E : Algebra (Carrier (FiniteAcceptance.Accepting L))) |
| 76 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 77 | E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 78 | quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 79 | {k : ℕ} (hk : 1 ≤ k) (x : Data (Carrier (FiniteAcceptance.Accepting L)) k) |
| 80 | (a : Carrier (FiniteAcceptance.Accepting L) k) |
| 81 | (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) : |
| 82 | ClassBelow (FiniteAcceptance.Accepting L) (E.eval k (delta x.1 x.2 a)) a |
| 83 | |
| 84 | axiom delta_in_context {A : RankedSet} (L : Algebras.Language A) |
| 85 | (E : Algebra (Carrier (FiniteAcceptance.Accepting L))) |
| 86 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 87 | E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 88 | quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 89 | {k : ℕ} (x : Data (Carrier (FiniteAcceptance.Accepting L)) k) |
| 90 | (a : Carrier (FiniteAcceptance.Accepting L) k) : |
| 91 | ClassBelow (FiniteAcceptance.Accepting L) (value E a x) |
| 92 | (value E (E.eval k (delta x.1 x.2 a)) x) |
| 93 | |
| 94 | axiom parallel_value {A : RankedSet} (E : Algebra A) {k : ℕ} |
| 95 | (B : Boundary k) (m : Fin (k + 1) → A 1) (a : A k) : |
| 96 | E.eval k (ofSetSystem (DeterministicElements.parallel (fun i => E.eval 1 (component B m a i)))) = |
| 97 | E.eval k (delta B m a) |
| 98 | |
| 100 | axiom acceptance_iff_dataBelow {A : RankedSet} (L : Algebras.Language A) |
| 101 | (E : Algebra (Carrier (FiniteAcceptance.Accepting L))) |
| 102 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 103 | E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 104 | quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 105 | {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k) |
| 106 | (a : Carrier (FiniteAcceptance.Accepting L) k) |
| 107 | (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) : |
| 108 | Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y ↔ |
| 109 | FiniteExtremal.DataBelow (FiniteAcceptance.Accepting L) x y |
| 110 | |
| 112 | def meetData {A : RankedSet} (E : Algebra A) {k : ℕ} (y z : Data A k) : Data A k := |
| 113 | (⟨y.1.root ∨ z.1.root, y.1.loops ∪ z.1.loops⟩, fun i => sumValue E (y.2 i) (z.2 i)) |
| 114 | |
| 115 | axiom accepting_meetData {A : RankedSet} (L : Algebras.Language A) |
| 116 | (E : Algebra (Carrier (FiniteAcceptance.Accepting L))) |
| 117 | (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n), |
| 118 | E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) = |
| 119 | quotientMap (FiniteAcceptance.Accepting L) n (flatten S)) |
| 120 | {k : ℕ} (hk : 1 ≤ k) (x y z : Data (Carrier (FiniteAcceptance.Accepting L)) k) |
| 121 | (a : Carrier (FiniteAcceptance.Accepting L) k) |
| 122 | (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) : |
| 123 | Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) (meetData E y z) ↔ |
| 124 | Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y ∧ |
| 125 | Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) z |
| 126 | |
| 127 | end Lax369799.SplitExtremal |
| 128 | |