Deterministic normal forms with identity continuations
Lax369799.DeterministicNormalForms · concepts/Lax369799/DeterministicNormalForms.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A closed deterministic context is represented by its hole value and the optional values of its unary continuations. A missing continuation copies the hole behavior. Vertex zero is the distinguished hole copy; the next vertex is the entry continuation; the remaining vertices correspond to hole directions. Every nonempty unary continuation returns to vertex zero.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.DeterministicPieces |
| 2 | import Lax369799.SystemEvaluation |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Deterministic normal forms with identity continuations |
| 7 | type: theorem |
| 8 | --- |
| 9 | A closed deterministic context is represented by its hole value and the |
| 10 | optional values of its unary continuations. A missing continuation copies |
| 11 | the hole behavior. Vertex zero is the distinguished hole copy; the next |
| 12 | vertex is the entry continuation; the remaining vertices correspond to |
| 13 | hole directions. Every nonempty unary continuation returns to vertex zero. |
| 14 | -/ |
| 15 | namespace Lax369799.DeterministicNormalForms |
| 16 | open RankedSystems Flattening Algebras DeterministicPieces |
| 17 | |
| 18 | /-- Missing unary pieces are copies of the distinguished vertex. -/ |
| 19 | def label {A : RankedSet} {k : ℕ} (a : A k) (P : Fin (k + 1) → Option (A 1)) : |
| 20 | Fin (k + 2) → Symbol A := |
| 21 | Fin.cases ⟨k, a⟩ (fun i => match P i with |
| 22 | | none => ⟨k, a⟩ |
| 23 | | some b => ⟨1, b⟩) |
| 24 | |
| 25 | def holeNext (k d : ℕ) : Fin (k + 2) := |
| 26 | if h : d < k then ⟨d + 2, Nat.add_lt_add_right h 2⟩ else 0 |
| 27 | |
| 28 | def next {A : RankedSet} {k : ℕ} (_a : A k) (P : Fin (k + 1) → Option (A 1)) |
| 29 | (v : Fin (k + 2)) (d : ℕ) : Fin (k + 2) := |
| 30 | Fin.cases (holeNext k d) (fun i => (P i).elim (holeNext k d) (fun _ => 0)) v |
| 31 | |
| 32 | def graph {A : RankedSet} {k : ℕ} (a : A k) (P : Fin (k + 1) → Option (A 1)) : |
| 33 | Presentation A 0 (Fin (k + 2)) where |
| 34 | label := label a P |
| 35 | initial := {1} |
| 36 | root := ∅ |
| 37 | edge := fun v d t => ∃ _hd : d < (label a P v).1, t = .inl (next a P v d) |
| 38 | direction_valid := fun _ _ _ h => h.choose |
| 39 | |
| 40 | |
| 41 | axiom pattern_exists {A : RankedSet} {k : ℕ} (a : A k) |
| 42 | (P : Fin (k + 1) → Option (A 1)) : |
| 43 | ∃ T : System A 0, T.val = trim (graph a P) |
| 44 | |
| 45 | axiom normal_form {A : RankedSet} (E : Algebra A) (hE : UnfoldInvariant E) |
| 46 | {k : ℕ} (C : SetContext A k 0) (hC : C.system.Deterministic) (S : System A k) : |
| 47 | ∃ U V : System A 0, |
| 48 | U.val = plug C S.val ∧ |
| 49 | V.val = trim (graph (E.eval k S) (fun i => (continuation C i).map (E.eval 1))) ∧ |
| 50 | E.eval 0 U = E.eval 0 V |
| 51 | |
| 52 | end Lax369799.DeterministicNormalForms |
| 53 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments