Recurring priorities in finite-state runs
Lax369799.WordParity · concepts/Lax369799/WordParity.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A run over finitely many states has a unique least recurring priority. Finite prefixes do not affect recurrence. A state with this least priority occurs twice arbitrarily far out, with no lower priority between the two occurrences; this is the cycle used in periodic branch arguments.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.UnfoldAutomata |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Recurring priorities in finite-state runs |
| 6 | type: theorem |
| 7 | --- |
| 8 | A run over finitely many states has a unique least recurring priority. |
| 9 | Finite prefixes do not affect recurrence. A state with this least priority |
| 10 | occurs twice arbitrarily far out, with no lower priority between the two |
| 11 | occurrences; this is the cycle used in periodic branch arguments. |
| 12 | -/ |
| 13 | namespace Lax369799.WordParity |
| 14 | |
| 15 | def Recurrent (p : ℕ → ℕ) (c : ℕ) : Prop := ∀ N, ∃ n, N ≤ n ∧ p n = c |
| 16 | |
| 17 | def LeastRecurring (p : ℕ → ℕ) (c : ℕ) : Prop := |
| 18 | Recurrent p c ∧ ∀ b, b < c → ∃ N, ∀ n, N ≤ n → p n ≠ b |
| 19 | |
| 20 | axiom least_recurring {Q : Type} [Finite Q] (priority : Q → ℕ) (r : ℕ → Q) : |
| 21 | ∃! c, LeastRecurring (fun n => priority (r n)) c |
| 22 | |
| 23 | axiom recurrent_shift (p : ℕ → ℕ) (c k : ℕ) : |
| 24 | Recurrent (fun n => p (n + k)) c ↔ Recurrent p c |
| 25 | |
| 26 | axiom minimum_cycle {Q : Type} [Finite Q] (priority : Q → ℕ) (r : ℕ → Q) |
| 27 | (c : ℕ) (hc : LeastRecurring (fun n => priority (r n)) c) (N : ℕ) : |
| 28 | ∃ i j, N ≤ i ∧ i < j ∧ r i = r j ∧ priority (r i) = c ∧ |
| 29 | ∀ k, i ≤ k → k ≤ j → c ≤ priority (r k) |
| 30 | |
| 31 | axiom acceptance_iff {u z : ℕ} (D : UnfoldAutomata.WordCondition u z) |
| 32 | (w : ℕ → Fin u) (c : ℕ) |
| 33 | (hc : LeastRecurring (fun n => D.priority (D.run w n)) c) : |
| 34 | D.AcceptsInfinite w ↔ Even c |
| 35 | |
| 36 | end Lax369799.WordParity |
| 37 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments