Ultimately periodic witnesses in finite parity graphs
Lax369799.PeriodicPaths · concepts/Lax369799/PeriodicPaths.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Every infinite path in a finite graph has an ultimately periodic path with the same initial vertex and least recurring priority. This supplies the periodic witness for checking a finite-state parity branch condition.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.WordParity |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Ultimately periodic witnesses in finite parity graphs |
| 6 | type: theorem |
| 7 | --- |
| 8 | Every infinite path in a finite graph has an ultimately periodic path |
| 9 | with the same initial vertex and least recurring priority. This supplies |
| 10 | the periodic witness for checking a finite-state parity branch condition. |
| 11 | -/ |
| 12 | namespace Lax369799.PeriodicPaths |
| 13 | |
| 14 | def UltimatelyPeriodic {Q : Type} (r : ℕ → Q) : Prop := |
| 15 | ∃ N p, 0 < p ∧ ∀ n, N ≤ n → r (n + p) = r n |
| 16 | |
| 17 | axiom periodic_witness {Q : Type} [Finite Q] (R : Q → Q → Prop) |
| 18 | (priority : Q → ℕ) (r : ℕ → Q) (hr : ∀ n, R (r n) (r (n + 1))) |
| 19 | (c : ℕ) (hc : WordParity.LeastRecurring (fun n => priority (r n)) c) : |
| 20 | ∃ s : ℕ → Q, s 0 = r 0 ∧ (∀ n, R (s n) (s (n + 1))) ∧ |
| 21 | UltimatelyPeriodic s ∧ WordParity.LeastRecurring (fun n => priority (s n)) c |
| 22 | |
| 23 | axiom periodic_test {Q : Type} [Finite Q] (R : Q → Q → Prop) |
| 24 | (priority : Q → ℕ) (q : Q) : |
| 25 | (∀ r : ℕ → Q, r 0 = q → (∀ n, R (r n) (r (n + 1))) → UltimatelyPeriodic r → |
| 26 | ∃ c, Even c ∧ WordParity.LeastRecurring (fun n => priority (r n)) c) ↔ |
| 27 | (∀ r : ℕ → Q, r 0 = q → (∀ n, R (r n) (r (n + 1))) → |
| 28 | ∃ c, Even c ∧ WordParity.LeastRecurring (fun n => priority (r n)) c) |
| 29 | |
| 30 | end Lax369799.PeriodicPaths |
| 31 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments