gen_k_server_uniform_path_cost
For a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the empty list, and for y :: ys it is hammingDist x y plus the path cost from y of ys. It is the total number of server moves along x, then the listed configurations in order.
Statement
def gen_k_server_uniform_path_cost {k m : ℕ} : (Fin k → Fin m) → List (Fin k → Fin m) → ℕ- Defined in
- arXiv:2610.37192, Sec. 2: cost of an offline solution, sum of Hamming distances between consecutive configurations
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 4
- gen_k_server_uniform_optFor a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some…
- gen_k_server_uniform_one_server_competitive_oneWith one server (k = 1, configurations Fin 1 → Fin m) and any start configuration a, there are transition probabilities P with…
- gen_k_server_uniform_log_competitiveFor every k ≥ 1, every m and every start configuration a : Fin k → Fin m of generalized k-server on k uniform metrics with m points each…
- gen_k_server_uniform_opt_singletonFor k ≥ 1 and configurations a, r : Fin k → Fin m, the offline optimum of the single request r from a is 0 if a i = r i for some i, and 1…
Read back from the Lean
Given implicit natural numbers k and m, this defines a function that takes an initial configuration x : Fin k → Fin m and a list of configurations List (Fin k → Fin m) and returns a natural number, defined recursively by:
- If the list is empty ([]), the result is 0.
- If the list has a head y and tail ys (y :: ys), the result is the Hamming distance between x and y (hammingDist x y) plus the result of the function called on y and ys.
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
/-- Movement cost of visiting the listed configurations in order from `x` (unit distances). -/ def gen_k_server_uniform_path_cost {k m : ℕ} : (Fin k → Fin m) → List (Fin k → Fin m) → ℕ | _, [] => 0 | x, y :: ys => hammingDist x y + gen_k_server_uniform_path_cost y ys