AFTD Auto-Formalizing Theoretical Domains

rank_potential

def

The rank potential function Φ for FIFO paging, defined as the sum of ranks of all pages currently in the online FIFO cache but absent from the offline cache.

Statement

def rank_potential {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) : ℕ
Defined in
arXiv:2610.18767 Section 3.2, Eq. (1)
Verified
20 Oct 2026
Axioms
none listed
Built on 2
  • FifoQueueA first-in first-out (FIFO) cache queue of capacity k over page type α, represented as a duplicate-free list of length k.
  • fifo_rankThe rank of a page in a FIFO queue of size k, ranging from 1 for the oldest page (next to be evicted) to k for the most recently fetched…
Used by 4

Read back from the Lean

For a type α with decidable equality, an implicit natural number k, a FIFO queue q : FifoQueue α k (a structure containing a list q.pages of length k with pairwise distinct elements), and a finite set cOpt : Finset α, rank_potential q cOpt is defined as the natural number obtained by summing fifo_rank q x over all elements x in the set difference q.pages.toFinset \ cOpt.

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

/-- Rank potential Φ summing ranks of online cached pages outside offline cache. -/
def rank_potential {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) : ℕ := ∑ x ∈ q.pages.toFinset \ cOpt, fifo_rank q x
See it in the graphDiscuss this resultChallenge it