FunctionQueryTree
inductive
A deterministic query decision tree for an unknown function from α to β returning a boolean.
Statement
inductive FunctionQueryTree (α β : Type*)
- Defined in
- arXiv:2611.02374 Sec. 2
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 2
- function_query_tree_depthThe maximum number of queries made by a query tree over all possible oracle responses.
- function_query_tree_evalEvaluates a function query tree on an input function f.
Read back from the Lean
An inductive type FunctionQueryTree α β parameterized by types α and β, with two constructors:
1. leaf : Bool → FunctionQueryTree α β, which creates a leaf node containing a Bool.
2. query : α → (β → FunctionQueryTree α β) → FunctionQueryTree α β, which creates an internal query node containing a query value in α and a branch function that maps each possible response in β to a sub-tree of type FunctionQueryTree α β.
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
/-- Deterministic adaptive query tree for evaluating an unknown function f : α → β with boolean output. -/ inductive FunctionQueryTree (α β : Type*) where | leaf : Bool → FunctionQueryTree α β | query : α → (β → FunctionQueryTree α β) → FunctionQueryTree α β