Evaluation of finite path graphs
Lax369799.FinitePathEvaluation · concepts/Lax369799/FinitePathEvaluation.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The graph with one vertex for each unary letter and a final nullary vertex evaluates to the iterated unary action on the nullary value.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.FiniteBranchWords |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Evaluation of finite path graphs |
| 6 | type: theorem |
| 7 | --- |
| 8 | The graph with one vertex for each unary letter and a final nullary |
| 9 | vertex evaluates to the iterated unary action on the nullary value. |
| 10 | -/ |
| 11 | namespace Lax369799.FinitePathEvaluation |
| 12 | open RankedSystems (RankedSet) |
| 13 | open FinitePresentations FiniteSyntacticAlgebra FiniteBranchWords |
| 14 | |
| 15 | def path {A : RankedSet} {k : ℕ} (w : Fin k → A 1) (a : A 0) : FiniteSystem A 0 where |
| 16 | size := k + 1 |
| 17 | graph := { |
| 18 | label := Fin.lastCases ⟨0, a⟩ (fun i => ⟨1, w i⟩) |
| 19 | initial := {0} |
| 20 | root := ∅ |
| 21 | edge := fun v d t => ∃ i : Fin k, v = i.castSucc ∧ d = 0 ∧ t = .inl i.succ |
| 22 | direction_valid := by rintro v d t ⟨i, rfl, rfl, rfl⟩; simp } |
| 23 | |
| 24 | |
| 25 | axiom evaluation {A : RankedSet} (E : Algebra A) {k : ℕ} |
| 26 | (w : Fin k → A 1) (a : A 0) : |
| 27 | E.eval 0 (path w a) = value E (List.ofFn w) a |
| 28 | |
| 29 | end Lax369799.FinitePathEvaluation |
| 30 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments