Algebraic evaluation and the words of a regular branch
Lax369799.UnarySystemEvaluation · concepts/Lax369799/UnarySystemEvaluation.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A closed deterministic system with only unary and nullary labels follows one branch. Its value is accepted exactly when its terminating branch word, or its infinite branch word, satisfies the corresponding algebraic word condition. This includes both chains ending at a nullary vertex and infinite branches represented by finite graphs.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.UnaryGraphEvaluation |
| 2 | import Lax369799.UnfoldAutomata |
| 3 | import Lax369799.FinitePathEvaluation |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Algebraic evaluation and the words of a regular branch |
| 8 | type: theorem |
| 9 | --- |
| 10 | A closed deterministic system with only unary and nullary labels follows |
| 11 | one branch. Its value is accepted exactly when its terminating branch |
| 12 | word, or its infinite branch word, satisfies the corresponding algebraic |
| 13 | word condition. This includes both chains ending at a nullary vertex and |
| 14 | infinite branches represented by finite graphs. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.UnarySystemEvaluation |
| 18 | open RankedSystems (RankedSet System) |
| 19 | open FinitePresentations FiniteSyntacticAlgebra UnfoldAutomata SetSystemAlgebras |
| 20 | |
| 21 | def Unary {A : RankedSet} (S : System A 0) : Prop := ∀ v, Rank S v ≤ 1 |
| 22 | |
| 23 | def unaryLabel {A : RankedSet} {S : System A 0} (hu : Unary S) |
| 24 | (v : S.val.Vertex) (d : Fin (Rank S v)) : A 1 := by |
| 25 | have h : Rank S v = 1 := by have := hu v; have := d.isLt; omega |
| 26 | exact h ▸ (S.val.graph.label v).2 |
| 27 | |
| 28 | def finiteWord {A : RankedSet} {S : System A 0} (hu : Unary S) |
| 29 | {k : ℕ} (b : FiniteBranch S k) : List (A 1) := |
| 30 | List.ofFn (fun i => unaryLabel hu (b.vertex i.castSucc) (b.direction i)) |
| 31 | |
| 32 | def leafValue {A : RankedSet} {S : System A 0} {k : ℕ} (b : FiniteBranch S k) : A 0 := |
| 33 | b.ends ▸ (S.val.graph.label (b.vertex (Fin.last k))).2 |
| 34 | |
| 35 | def infiniteWord {A : RankedSet} {S : System A 0} (hu : Unary S) |
| 36 | (b : InfiniteBranch S) : ℕ → A 1 := fun n => unaryLabel hu (b.vertex n) (b.direction n) |
| 37 | |
| 38 | axiom agreement {A : RankedSet} (E : SetAlgebra A) |
| 39 | (F : Set (A 0)) [Finite (A 1)] (S : System A 0) (hu : Unary S) : |
| 40 | E.eval 0 (ofSetSystem S.val) ∈ F ↔ |
| 41 | (∀ k (b : FiniteBranch S k), FiniteBranchWords.value E.toAlgebra (finiteWord hu b) (leafValue b) ∈ F) ∧ |
| 42 | (∀ b : InfiniteBranch S, AlgebraicOmegaWords.Accepts E.toAlgebra F (infiniteWord hu b)) |
| 43 | |
| 44 | end Lax369799.UnarySystemEvaluation |
| 45 |
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments