AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_is_schedule

def

For a natural number k, a family of spaces M indexed by Fin k, a list of requests ρ, and a list of configurations sched, sched is a valid schedule for ρ if sched and ρ have the same length and for every corresponding pair (x, r) in sched and ρ, x serves r (i.e. x i = r i for some i in Fin k).

Statement

def uniform_kserver_is_schedule {k : ℕ} {M : Fin k → Type*} (ρ : List (∀ i, M i)) (sched : List (∀ i, M i)) : Prop
Defined in
scout/2610-37192-tight-bounds-for-randomized-generalized-k-server-on-uniform.md:340
Verified
28 Oct 2026
Axioms
none listed
Used by 3
  • uniform_kserver_det_schedule_is_scheduleFor a natural number k, a family of types M indexed by Fin k, an algorithm A : List (∀ i, M i) → (∀ i, M i) satisfying…
  • uniform_kserver_optFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of requests…
  • uniform_kserver_det_k_one_competitiveFor generalized 1-server on any family of uniform metric spaces M indexed by Fin 1 with decidable equality and any initial configuration a…

Read back from the Lean

Given a natural number k and a family of types M indexed by Fin k, and two lists ρ and sched of configurations (elements of ∀ i : Fin k, M i), uniform_kserver_is_schedule asserts that sched and ρ have the same length, and for every corresponding pair (s, r) in sched.zip ρ, there exists an index i : Fin k such that s i = r i (the schedule agrees with ρ on at least one coordinate i).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An offline schedule is valid for request sequence ρ if it has the same length and each step serves the corresponding request. -/
def uniform_kserver_is_schedule {k : ℕ} {M : Fin k → Type*} (ρ : List (∀ i, M i)) (sched : List (∀ i, M i)) : Prop :=
  sched.length = ρ.length ∧ ∀ pair ∈ sched.zip ρ, ∃ i : Fin k, pair.1 i = pair.2 i
See it in the graphDiscuss this resultChallenge it