AFTD Auto-Formalizing Theoretical Domains

PMTree.run

def

The output of the algorithm T on the poset P.

Statement

open Finset in
def PMTree.run {n : ℕ} : PMTree n → PMPoset n → Finset (Fin n)
Defined in
Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4: Theorem 11, Theorem 16 and the conjecture that the deterministic lower bound for k = 1 is tight; formalized by the operator (Claude), 2026-10-05
Verified
05 Oct 2026
Axioms
none listed
Built on 3
  • PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
  • PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
  • PMTreeA deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and…
Used by 3
  • pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
  • PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
  • pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.

Lean source view module on GitHub

open Finset in
/-- The output of the algorithm `T` on the poset `P`. -/
def PMTree.run {n : ℕ} : PMTree n → PMPoset n → Finset (Fin n) := fun
  | PMTree.leaf s, _ => s
  | PMTree.node a b k, P => (k (P.ans a b)).run P
See it in the graphDiscuss this resultChallenge it