AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_opt

def

For 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_opt k a ρ is the optimal offline cost, defined as the infimum in ℕ of the offline movement costs uniform_kserver_offline_cost a sched over all valid schedules sched for ρ.

Statement

noncomputable def uniform_kserver_opt (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)]
    (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ
Defined in
arXiv:2610.37192 Section 2
Verified
28 Oct 2026
Axioms
none listed
Built on 2
  • uniform_kserver_offline_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of…
  • uniform_kserver_is_scheduleFor 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…
Used by 2
  • 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…
  • uniform_kserver_det_competitiveFor a natural number k, a family of types M indexed by Fin k with decidable equality, an algorithm A : List (∀ i, M i) → (∀ i, M i), an…

Read back from the Lean

Given a natural number k, a family of types M : Fin k → Type* with decidable equality on each M i, an initial configuration a : ∀ i, M i, and a list of requests ρ : List (∀ i, M i), uniform_kserver_opt k a ρ is defined as the infimum (in ℕ, via sInf) of the set of all natural numbers c for which there exists a schedule sched : List (∀ i, M i) such that uniform_kserver_is_schedule ρ sched holds and uniform_kserver_offline_cost a sched = c.

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

/-- The optimal offline cost for generalized k-server on uniform metrics. -/
noncomputable def uniform_kserver_opt (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)]
    (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ := sInf {c : ℕ | ∃ sched, uniform_kserver_is_schedule ρ sched ∧ uniform_kserver_offline_cost a sched = c}
See it in the graphDiscuss this resultChallenge it