AFTD Auto-Formalizing Theoretical Domains

PagingWithDelayExecution

structure

A structure PagingWithDelayExecution parameterized by page type α with decidable equality and cache capacity k : ℕ, consisting of the number of payments P : ℕ, offline fetch count F_opt : ℕ, offline delay D_opt : ℝ with 0 ≤ D_opt, a list of payment windows of length P, and an accounting property that (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt).

Statement

structure PagingWithDelayExecution (α : Type*) [DecidableEq α] (k : ℕ)
Defined in
arXiv:2610.18767 Section 2 & Section 3
Verified
21 Oct 2026
Axioms
none listed
Built on 1
  • PaymentWindowA structure PaymentWindow parameterized by page type α and cache capacity k : ℕ, consisting of a requested page : α, offline fetch count…
Used by 3
  • paging_with_delay_alg_costThe total cost incurred by the 1-FIFO algorithm in a paging with delay execution exec, defined as 2 * (exec.P : ℝ).
  • paging_with_delay_opt_costThe total offline cost in a paging with delay execution exec, defined as the sum of offline fetches and offline delay: (exec.F_opt : ℝ) +…
  • one_fifo_strictly_competitive_paging_with_delayFor any type α with decidable equality, any natural number k, and any paging with delay execution exec of type PagingWithDelayExecution α…

Read back from the Lean

A structure PagingWithDelayExecution, parameterized by a type α with decidable equality and a natural number k, bundling: 1. P : ℕ 2. F_opt : ℕ 3. D_opt : ℝ 4. A proof h_delay_nonneg that 0 ≤ D_opt 5. A list windows of elements of type PaymentWindow α k 6. A proof h_windows_len that the length of windows is P 7. A proof h_accounting that (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt).

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

/-- Execution of 1-FIFO and offline algorithm for paging with delay. -/
structure PagingWithDelayExecution (α : Type*) [DecidableEq α] (k : ℕ) where
  P : ℕ
  F_opt : ℕ
  D_opt : ℝ
  h_delay_nonneg : 0 ≤ D_opt
  windows : List (PaymentWindow α k)
  h_windows_len : windows.length = P
  h_accounting : (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt)
See it in the graphDiscuss this resultChallenge it