Evaluation of finite unary branch graphs
Lax369799.UnaryGraphEvaluation · concepts/Lax369799/UnaryGraphEvaluation.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite unary graph generated by its initial vertex evaluates like any lasso obtained by cutting its path at a repeated vertex and composing the two nonempty words. Stable factorization proves that its value is accepted exactly when its unfolded word satisfies the algebraic omega condition.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.SetSystemAlgebras |
| 2 | import Lax369799.AlgebraicOmegaWords |
| 3 | import Lax369799.UnaryChains |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Evaluation of finite unary branch graphs |
| 8 | type: theorem |
| 9 | --- |
| 10 | A finite unary graph generated by its initial vertex evaluates like any |
| 11 | lasso obtained by cutting its path at a repeated vertex and composing the |
| 12 | two nonempty words. Stable factorization proves that its value is accepted |
| 13 | exactly when its unfolded word satisfies the algebraic omega condition. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.UnaryGraphEvaluation |
| 17 | open RankedSystems (RankedSet Presentation) |
| 18 | open FinitePresentations FiniteSyntacticAlgebra UnaryFactorization SetSystemAlgebras |
| 19 | |
| 20 | def trace {V : Type} (next : V → V) (start : V) : ℕ → V |
| 21 | | 0 => start |
| 22 | | n + 1 => next (trace next start n) |
| 23 | |
| 24 | def graph {A : RankedSet} {V : Type} (next : V → V) (start : V) (b : V → A 1) : |
| 25 | Presentation A 0 V where |
| 26 | label := fun v => ⟨1, b v⟩ |
| 27 | initial := {start} |
| 28 | root := ∅ |
| 29 | edge := fun v d t => d = 0 ∧ t = .inl (next v) |
| 30 | direction_valid := by rintro v d t ⟨rfl, _⟩; exact Nat.zero_lt_one |
| 31 | |
| 32 | axiom cycle_folding {A : RankedSet} (E : SetAlgebra A) |
| 33 | {V : Type} [Fintype V] (next : V → V) (start : V) (b : V → A 1) |
| 34 | (hreach : ∀ v, ∃ n, trace next start n = v) (m k : ℕ) |
| 35 | (hclose : trace next start (m + k + 2) = trace next start (m + 1)) : |
| 36 | E.eval 0 (enumerate (graph next start b)) = E.eval 0 (lasso |
| 37 | (block E.toAlgebra (b ∘ trace next start) 0 (m + 1)) |
| 38 | (block E.toAlgebra (b ∘ trace next start) (m + 1) (m + k + 2))) |
| 39 | |
| 40 | axiom agreement {A : RankedSet} (E : SetAlgebra A) |
| 41 | (F : Set (A 0)) [Finite (A 1)] {V : Type} [Fintype V] |
| 42 | (next : V → V) (start : V) (b : V → A 1) (hreach : ∀ v, ∃ n, trace next start n = v) : |
| 43 | E.eval 0 (enumerate (graph next start b)) ∈ F ↔ |
| 44 | AlgebraicOmegaWords.Accepts E.toAlgebra F (b ∘ trace next start) |
| 45 | |
| 46 | end Lax369799.UnaryGraphEvaluation |
| 47 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments