AFTD Auto-Formalizing Theoretical Domains

StochasticMstStrategy

inductive

An adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further queries) or an internal node that queries an edge e and branches to a 0-child (on outcome 0) and a 1-child (on outcome 1).

Statement

inductive StochasticMstStrategy (α : Type*) : Type _
Defined in
arXiv:2610.40844 Section 3
Verified
07 Nov 2026
Axioms
none listed
Used by 8
  • is_optimal_stochastic_mst_strategyA strategy T is an optimal strategy solving the adaptive MST identification problem for graph G with edge probabilities p if T solves the…
  • stochastic_mst_strategy_costFor an edge probability function p assigning each edge e the probability that e has weight 1, the expected number of queries of a strategy…
  • stochastic_mst_solvesA strategy T solves the adaptive MST identification problem for G if it solves the problem starting from the empty state of contracted and…
  • tutte_strategy_solves_stochastic_mstFor any graph G, every Tutte strategy T for G solves the adaptive MST identification problem for G.
  • stochastic_mst_is_tutteA strategy T is a Tutte strategy for G if it satisfies the Tutte strategy predicate starting from the empty state of contracted and…
  • stochastic_mst_solves_auxFrom state (Z, D) of contracted edges Z and deleted edges D, a strategy solves the adaptive MST identification problem for G if at every…
  • stochastic_mst_query_continuation_solvesFor a graph G and an edge e that is query-eligible at the initial state (∅, ∅), the strategy querying e with children s₀ and s₁ solves the…
  • stochastic_mst_is_tutte_auxFrom state (Z, D) of contracted edges Z and deleted edges D, a strategy is a Tutte strategy for G if at a leaf no edge of G is…

Read back from the Lean

The inductive type StochasticMstStrategy α, parameterized by a type α, defined with two constructors: 1. leaf, which takes no arguments and constructs a StochasticMstStrategy α; 2. query, which takes an element e : α and two subtrees s₀, s₁ : StochasticMstStrategy α, constructing a StochasticMstStrategy α. This defines a binary tree where internal nodes are labeled with elements of α and leaves are unlabeled.

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

/-- An adaptive querying strategy for binary stochastic MST identification as a binary decision tree. -/
inductive StochasticMstStrategy (α : Type*) : Type _ | leaf : StochasticMstStrategy α
| query (e : α) (s₀ s₁ : StochasticMstStrategy α) : StochasticMstStrategy α
See it in the graphDiscuss this resultChallenge it