AFTD Auto-Formalizing Theoretical Domains

tarski_query_tree_bind

def

Sequential composition of query trees: run the tree, then feed its output point into the continuation g to obtain the tree that is actually executed.

Statement

def tarski_query_tree_bind {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k) :
    TarskiQueryTree n k → TarskiQueryTree n k
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
none listed
Built on 1
  • TarskiQueryTreeA deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal…
Used by 2
  • tarski_box_query_le_succ_halvingOne dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most…
  • tarski_query_tree_bind_specRun/cost law for sequential composition: the run of a bind is the run of the continuation g at the output of the first tree, and the cost…

Lean source view module on GitHub

/-- Sequential composition: run a query tree, then continue with the tree g applied to its output. -/
def tarski_query_tree_bind {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k) :
    TarskiQueryTree n k → TarskiQueryTree n k := fun _t => match _t with
  | .output x => g x
  | .query x k' => .query x (fun v => tarski_query_tree_bind g (k' v))
See it in the graphDiscuss this resultChallenge it