instanceHorizon
def
The finite time horizon of a list of deadline requests, defined as one more than the maximum deadline, or zero if empty.
Statement
def instanceHorizon {α : Type*} (reqs : List (DeadlineRequest α)) : ℕ
- Defined in
- arXiv:2610.18767 Sec. 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 1
- DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
- Used by 6
- not_deadline_paging_upper_bound_k_plus_oneThe statement
deadline_paging_upper_bound_k_plus_oneis false: The statement (for every k≥1, every finite α with card ≥ k+1, every C₀ of… - deadline_paging_min_cost_schedule_existsEvery feasible deadline-paging instance admits a feasible schedule whose fetch cost over the instance horizon is minimal among all…
- deadline_paging_cost_zero_iff_pages_subset_cacheA feasible instance can be served at fetch cost zero iff every requested page is already in the initial cache.
- deadline_paging_opt_cost_ge_pages_outside_cacheEvery feasible schedule must fetch each requested page outside the initial cache at least once, so its fetch cost is at least the number…
- IsCompetitiveRatioA schedule generator Alg is ρ-competitive for cache capacity k and initial cache C₀ if it is online, produces a feasible schedule whenever…
- deadline_paging_lower_bound_k_plus_halfFor every cache capacity k ≥ 1, every finite page universe α with at least k + 2 pages, every initial cache C₀ of size k, every schedule…
- not_deadline_paging_upper_bound_k_plus_oneThe statement
Read back from the Lean
For a type α and a list reqs of DeadlineRequest α, instanceHorizon reqs is the natural number defined as the right fold over reqs starting from 0 with the operation fun r m => max (r.deadline + 1) m. In other words, it is 0 if reqs is empty, and max_{r ∈ reqs} (r.deadline + 1) (one greater than the maximum deadline among all requests in reqs) if reqs is non-empty.
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 time horizon of a list of deadline requests. -/ def instanceHorizon {α : Type*} (reqs : List (DeadlineRequest α)) : ℕ := reqs.foldr (fun r m => max (r.deadline + 1) m) 0