AFTD Auto-Formalizing Theoretical Domains

function_query_tree_depth

def

The maximum number of queries made by a query tree over all possible oracle responses.

Statement

def function_query_tree_depth {α β : Type*} [Fintype β] (t : FunctionQueryTree α β) : ℕ
Defined in
arXiv:2611.02374 Sec. 2
Verified
05 Nov 2026
Axioms
none listed
Built on 1
  • FunctionQueryTreeA deterministic query decision tree for an unknown function from α to β returning a boolean.

Read back from the Lean

For any types α and β where β is finite ([Fintype β]), function_query_tree_depth is the function mapping a tree t : FunctionQueryTree α β to a natural number (ℕ), defined recursively: - A leaf node (.leaf _) has depth 0. - A query node (.query _ next), where next : β → FunctionQueryTree α β, has depth 1 plus the supremum over all y : β (in Finset.univ) of the depth of next y (which evaluates to the maximum depth among all children, or 0 if β is empty).

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

/-- Worst-case query depth of a query tree. -/
def function_query_tree_depth {α β : Type*} [Fintype β] (t : FunctionQueryTree α β) : ℕ :=
  match t with
  | .leaf _ => 0
  | .query _ next => 1 + Finset.sup Finset.univ (fun y => function_query_tree_depth (next y))
See it in the graphDiscuss this resultChallenge it