AFTD Auto-Formalizing Theoretical Domains

IsFeasibleSchedule

def

A schedule of cache configurations of size at most k is feasible for a list of deadline requests starting from initial cache C₀ if it starts at C₀, keeps cache size at most k at all times, and caches each requested page at some time between its arrival and deadline.

Statement

def IsFeasibleSchedule {α : Type*} (k : ℕ) (C₀ : Finset α)
    (sched : ℕ → Finset α) (reqs : List (DeadlineRequest α)) : 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 8

Read back from the Lean

Given a type α, a natural number k, an initial finite set C₀ : Finset α, a schedule sched : ℕ → Finset α, and a list reqs of deadline requests (each having a page r.page : α, arrival time r.arrival : ℕ, deadline r.deadline : ℕ, and a proof that r.arrival ≤ r.deadline), IsFeasibleSchedule k C₀ sched reqs asserts that: 1. sched 0 = C₀ (the schedule starts at configuration C₀ at time 0), 2. For all t : ℕ, the cardinality of sched t is at most k, and 3. For every request r in reqs, there exists a time t : ℕ such that r.arrival ≤ t, t ≤ r.deadline, and r.page ∈ sched 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

/-- Feasibility of a cache schedule for an instance of paging with deadlines. -/
def IsFeasibleSchedule {α : Type*} (k : ℕ) (C₀ : Finset α)
    (sched : ℕ → Finset α) (reqs : List (DeadlineRequest α)) : Prop :=
  sched 0 = C₀ ∧
  (∀ t, (sched t).card ≤ k) ∧
  (∀ r ∈ reqs, ∃ t, r.arrival ≤ t ∧ t ≤ r.deadline ∧ r.page ∈ sched t)
See it in the graphDiscuss this resultChallenge it