Testing infinite runs on finite branch graphs
Lax369799.RegularBranchWords · concepts/Lax369799/RegularBranchWords.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite branch graph unfolds to an ultimately periodic branch, and every ultimately periodic branch has such a presentation. Thus a parity condition holds on all infinite branches exactly when it holds on the unfoldings of all finite branch graphs.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.RunBranchObservations |
| 2 | import Lax369799.UnfoldBranches |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Testing infinite runs on finite branch graphs |
| 7 | type: theorem |
| 8 | --- |
| 9 | A finite branch graph unfolds to an ultimately periodic branch, and every |
| 10 | ultimately periodic branch has such a presentation. Thus a parity condition |
| 11 | holds on all infinite branches exactly when it holds on the unfoldings of |
| 12 | all finite branch graphs. |
| 13 | -/ |
| 14 | namespace Lax369799.RegularBranchWords |
| 15 | open RankedSystems (RankedSet System) |
| 16 | open UnfoldAutomata RunBranchObservations |
| 17 | |
| 18 | def position {A : RankedSet} {S : System A 0} (b : RegularBranch S) : ℕ → Fin b.size |
| 19 | | 0 => b.start |
| 20 | | n + 1 => b.next (position b n) |
| 21 | |
| 22 | def trace {A : RankedSet} {S : System A 0} (b : RegularBranch S) : InfiniteBranch S where |
| 23 | vertex := fun n => b.vertex (position b n) |
| 24 | direction := fun n => b.direction (position b n) |
| 25 | starts := b.starts |
| 26 | follows := fun n => b.follows (position b n) |
| 27 | |
| 28 | axiom periodic {A : RankedSet} {S : System A 0} (b : RegularBranch S) : |
| 29 | UnfoldBranches.Periodic (trace b) |
| 30 | |
| 31 | axiom represents {A : RankedSet} {S : System A 0} (b : InfiniteBranch S) |
| 32 | (hb : UnfoldBranches.Periodic b) : |
| 33 | ∃ c : RegularBranch S, ∀ n, |
| 34 | (⟨(trace c).vertex n, (trace c).direction n⟩ : (v : S.val.Vertex) × Fin (Rank S v)) = |
| 35 | ⟨b.vertex n, b.direction n⟩ |
| 36 | |
| 37 | axiom regular_test {A : RankedSet} (M : UnfoldAutomaton A) (S : System A 0) (r : Run M S) : |
| 38 | (∀ b : RegularBranch S, M.condition.AcceptsInfinite |
| 39 | (fun n => r.edgeType ((trace b).vertex n) ((trace b).direction n))) ↔ |
| 40 | (∀ b : InfiniteBranch S, M.condition.AcceptsInfinite |
| 41 | (fun n => r.edgeType (b.vertex n) (b.direction n))) |
| 42 | |
| 43 | end Lax369799.RegularBranchWords |
| 44 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments