AFTD Auto-Formalizing Theoretical Domains

pmAlg

def

The candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal elements of the prefix; a new element is compared with the candidates one by one. m is the number of elements still to scan.

Statement

open Finset in
def pmAlg {n : ℕ} : ℕ → ℕ → List (Fin n) → PMTree n
Defined in
Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4, Theorem 11 (the candidate-set algorithm for the minimal elements); specialised to width 2
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • PMAnsThe three possible answers of a comparison query (a, b) on a poset: a ≺ b, b ≺ a, or a ∥ b (incomparable). Setting of arXiv 0707.1532…
  • 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 5
  • pm_alg_correctThe algorithm is correct on every width-2 poset.
  • pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
  • pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
  • pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
  • pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.

Lean source view module on GitHub

open Finset in
/-- The candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal elements of the prefix; a new element is compared with the candidates one by one. `m` is the number of elements still to scan. -/
def pmAlg {n : ℕ} : ℕ → ℕ → List (Fin n) → PMTree n := fun
  | 0, _, cs => PMTree.leaf cs.toFinset
  | m + 1, k, cs =>
    if h : k < n then
      match cs with
      | [] => pmAlg m (k + 1) [⟨k, h⟩]
      | [t] => PMTree.node ⟨k, h⟩ t (fun r => match r with
          | PMAns.lt => pmAlg m (k + 1) [⟨k, h⟩]
          | PMAns.gt => pmAlg m (k + 1) [t]
          | PMAns.inc => pmAlg m (k + 1) [t, ⟨k, h⟩])
      | [t1, t2] => PMTree.node ⟨k, h⟩ t1 (fun r => match r with
          | PMAns.gt => pmAlg m (k + 1) [t1, t2]
          | PMAns.lt => PMTree.node ⟨k, h⟩ t2 (fun r2 => match r2 with
              | PMAns.lt => pmAlg m (k + 1) [⟨k, h⟩]
              | PMAns.gt => pmAlg m (k + 1) [t1, t2]
              | PMAns.inc => pmAlg m (k + 1) [t2, ⟨k, h⟩])
          | PMAns.inc => PMTree.node ⟨k, h⟩ t2 (fun r2 => match r2 with
              | PMAns.gt => pmAlg m (k + 1) [t1, t2]
              | PMAns.lt => pmAlg m (k + 1) [t1, ⟨k, h⟩]
              | PMAns.inc => pmAlg m (k + 1) [t1, t2]))
      | _ => PMTree.leaf ∅
    else PMTree.leaf cs.toFinset
See it in the graphDiscuss this resultChallenge it