AFTD Auto-Formalizing Theoretical Domains

IsOnlineClairvoyantScheduleGen

def

A deterministic clairvoyant online schedule generator on lists of requests produces a cache configuration at time t that depends only on the list of requests with arrival time at most t; specifically, for any two lists of deadline requests reqs₁ and reqs₂, if their sublists of requests arriving at or before t are equal, then the generator produces the same cache configuration at time t.

Statement

def IsOnlineClairvoyantScheduleGen {α : Type*}
    (Alg : List (DeadlineRequest α) → (ℕ → Finset α)) : Prop
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 3
  • not_deadline_paging_upper_bound_k_plus_oneThe statement deadline_paging_upper_bound_k_plus_one is false: The statement (for every k≥1, every finite α with card ≥ k+1, every C₀ of…
  • 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…

Read back from the Lean

For a type α, a function Alg : List (DeadlineRequest α) → ℕ → Finset α satisfies IsOnlineClairvoyantScheduleGen Alg if and only if for all request lists reqs₁ and reqs₂ and for all time steps t : ℕ, whenever the sublist of requests in reqs₁ with arrival time arrival ≤ t is identical (in elements and order) to the sublist of requests in reqs₂ with arrival time arrival ≤ t, the set of pages scheduled at time t, Alg reqs₁ t, is equal to Alg reqs₂ t.

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

/-- Causality condition defining a deterministic clairvoyant online schedule generator on lists of requests. -/
def IsOnlineClairvoyantScheduleGen {α : Type*}
    (Alg : List (DeadlineRequest α) → (ℕ → Finset α)) : Prop :=
  ∀ reqs₁ reqs₂ : List (DeadlineRequest α), ∀ t : ℕ,
    reqs₁.filter (fun r => r.arrival ≤ t) = reqs₂.filter (fun r => r.arrival ≤ t) →
      Alg reqs₁ t = Alg reqs₂ t
See it in the graphDiscuss this resultChallenge it