AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_det_alg_serves

def

A deterministic online algorithm A taking a request list to a configuration serves requests if for every list of earlier requests ρ and current request r, the configuration A (ρ ++ [r]) serves r (meaning A (ρ ++ [r]) i = r i for some coordinate i).

Statement

def uniform_kserver_det_alg_serves {k : ℕ} {M : Fin k → Type*}
    (A : List (∀ i, M i) → (∀ i, M i)) : Prop
Defined in
arXiv:2610.37192 Sec. 6
Verified
30 Oct 2026
Axioms
none listed
Built on 1
  • uniform_kserver_servesFor a natural number k, a family of uniform metric spaces M indexed by Fin k, and configurations x, r in the product space over Fin k, x…
Used by 3

Read back from the Lean

Given a natural number $k$ and a family of types $M : \text{Fin } k \to \text{Type*}$, a deterministic algorithm $A : \text{List} (\forall i, M i) \to (\forall i, M i)$ satisfies uniform_kserver_det_alg_serves if for every list of configurations $\rho : \text{List} (\forall i, M i)$ and every configuration $r : \forall i, M i$, the configuration output by $A$ on the extended history $\rho ++ [r]$ serves $r$ according to uniform_kserver_serves.

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

/-- A deterministic online algorithm serves requests if it serves the latest request on every sequence. -/
def uniform_kserver_det_alg_serves {k : ℕ} {M : Fin k → Type*}
    (A : List (∀ i, M i) → (∀ i, M i)) : Prop :=
  ∀ (ρ : List (∀ i, M i)) (r : ∀ i, M i), uniform_kserver_serves (A (ρ ++ [r])) r
See it in the graphDiscuss this resultChallenge it