While this submission is a draft, it cannot be used by other submissions.

Recurring priorities in finite-state runs

Lax369799.WordParity · concepts/Lax369799/WordParity.lean · lax-369799

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    6 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    1 acceptance_iff proven

    2 least_recurring proven

    3 minimum_cycle proven

    4 recurrent_shift proven

    Lean source view on GitHub

    1import Lax369799.UnfoldAutomata
    2
    3/-!
    4---
    5title: Recurring priorities in finite-state runs
    6type: theorem
    7---
    8A run over finitely many states has a unique least recurring priority.
    9Finite prefixes do not affect recurrence. A state with this least priority
    10occurs twice arbitrarily far out, with no lower priority between the two
    11occurrences; this is the cycle used in periodic branch arguments.
    12-/
    13namespace Lax369799.WordParity
    14
    15def Recurrent (p : ℕ → ℕ) (c : ℕ) : Prop := ∀ N, ∃ n, N ≤ n ∧ p n = c
    16
    17def LeastRecurring (p : ℕ → ℕ) (c : ℕ) : Prop :=
    18 Recurrent p c ∧ ∀ b, b < c → ∃ N, ∀ n, N ≤ n → p n ≠ b
    19
    20axiom least_recurring {Q : Type} [Finite Q] (priority : Q → ℕ) (r : ℕ → Q) :
    21 ∃! c, LeastRecurring (fun n => priority (r n)) c
    22
    23axiom recurrent_shift (p : ℕ → ℕ) (c k : ℕ) :
    24 Recurrent (fun n => p (n + k)) c ↔ Recurrent p c
    25
    26axiom 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
    31axiom 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
    36end Lax369799.WordParity
    37
    Show ProofShow ProofShow ProofShow Proof
    Builds on
    Used by
    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…