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))