moving_target_strategy_successful
Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, an accuracy threshold s : ℕ, a strategy strat : MovingTargetStrategy V, and a candidate set D : Finset V, moving_target_strategy_successful G s strat D is a proposition defined by recursion on strat: if strat is stop, then D.card ≤ s; if strat is query Q on_false on_true, let C := closed_neighborhood G D in ((C \ Q).Nonempty → moving_target_strategy_successful G s on_false (C \ Q)) ∧ ((C ∩ Q).Nonempty → moving_target_strategy_successful G s on_true (C ∩ Q)).
Statement
def moving_target_strategy_successful {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s : ℕ) : MovingTargetStrategy V → Finset V → Prop
- Defined in
- arXiv:2611.01281 Definition 2.1
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 2
- MovingTargetStrategyAn inductive datatype
MovingTargetStrategyparameterized by a typeV : Type*, with two constructors:stop : MovingTargetStrategy V… - closed_neighborhoodGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset A : Finset V,…
- MovingTargetStrategyAn inductive datatype
- Used by 4
- three_by_three_torus_moving_target_accuracy_exactOn the 3-by-3 torus C_3 □ C_3, the minimum achievable moving-target localization accuracy starting from the candidate set of all vertices…
- moving_target_strategy_stop_successfulFor any finite type V with decidable equality and simple graph G on V with decidable adjacency, the immediate stopping strategy…
- moving_target_grid_accuracy_le_minFor all M, N ≥ 1, on the M × N rectangular grid (vertices Fin M × Fin N, adjacent when they differ by one in exactly one coordinate) there…
- three_by_cycle_torus_moving_target_accuracy_le_ceilFor every integer n ≥ 3, there exists an adaptive search strategy for a moving target on the 3-by-n torus C_3 □ C_n achieving accuracy at…
Read back from the Lean
Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a natural number s, moving_target_strategy_successful G s is a recursively defined predicate on a strategy tree (of type MovingTargetStrategy V) and a set of candidate vertices D : Finset V:
- If the strategy is .stop, it asserts that the cardinality of D is at most s (D.card ≤ s).
- If the strategy is .query Q on_false on_true for a query set Q : Finset V and sub-strategies on_false and on_true:
Let C be the closed neighborhood of D in G. The predicate asserts the conjunction of:
1. If C \ Q is nonempty, then moving_target_strategy_successful G s on_false (C \ Q) holds.
2. If C ∩ Q is nonempty, then moving_target_strategy_successful G s on_true (C ∩ Q) holds.
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
/-- Whether an adaptive search strategy is successful with accuracy s starting from a candidate set. -/ def moving_target_strategy_successful {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s : ℕ) : MovingTargetStrategy V → Finset V → Prop | .stop, D => D.card ≤ s | .query Q on_false on_true, D => let C := closed_neighborhood G D ((C \ Q).Nonempty → moving_target_strategy_successful G s on_false (C \ Q)) ∧ ((C ∩ Q).Nonempty → moving_target_strategy_successful G s on_true (C ∩ Q))