AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_det_cost

def

For 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 initial configuration a : ∀ i, M i, and a request sequence ρ : List (∀ i, M i), uniform_kserver_det_cost A a ρ is the offline movement cost uniform_kserver_offline_cost a (uniform_kserver_det_schedule A ρ).

Statement

def uniform_kserver_det_cost {k : ℕ} {M : Fin k → Type*} [∀ i, DecidableEq (M i)]
    (A : List (∀ i, M i) → (∀ i, M i)) (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ
Defined in
arXiv:2610.37192 Sec. 6
Verified
30 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_det_scheduleGiven types α and β, a mapping A : List α → β, and an input list ρ : List α, uniform_kserver_det_schedule A ρ is the list of elements of β…
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

A definition of uniform_kserver_det_cost: given a number of servers k : ℕ, a family of types M : Fin k → Type* with decidable equality on each M i, a deterministic algorithm A : List (∀ i, M i) → (∀ i, M i), an initial configuration a : ∀ i, M i, and an input sequence ρ : List (∀ i, M i), it computes the total transition cost (as a natural number) incurred by running A starting from configuration a on ρ. Specifically, A is evaluated on each non-empty prefix ρ.take (t + 1) for t ∈ {0, ..., ρ.length - 1} to produce a schedule of configurations. The total cost is the sum of the Hamming distances (the number of coordinates i : Fin k that differ) between consecutive configurations along the path, beginning from a to the first configuration A (ρ.take 1), and then between each successive pair in the schedule.

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

/-- Total movement cost incurred by deterministic algorithm A on ρ starting from a. -/
def uniform_kserver_det_cost {k : ℕ} {M : Fin k → Type*} [∀ i, DecidableEq (M i)]
    (A : List (∀ i, M i) → (∀ i, M i)) (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ :=
  uniform_kserver_offline_cost a (uniform_kserver_det_schedule A ρ)
See it in the graphDiscuss this resultChallenge it