Proof of Theorem 1, p. 4 — layer d of the breadth-first search is the set of intervals at δ′-distance exactly d from the minimal intervals
ProvedMonoReset.IntervalBFS.bfs_layersLet be any automaton (monotonicity is not needed) and . Consider the breadth-first search of the algorithm: layer is the set of minimal intervals containing , and layer consists of the intervals , computed by the table-based evaluation, for in layer and , that lie in no earlier layer. Then for every and every interval ,
i.e. some word of length leads a minimal interval containing to , and no shorter word does. Here " leads to " means that applying the table-based transitions letter by letter from ends at (never at ).
This is the correctness of "the standard breadth first search algorithm" in the proof of Theorem 1: the first layer containing a singleton interval is at the minimum distance of any singleton.
Formalization Note States are Fin n, with the element and the cyclic order ; letters are Fin k; a word is a list read left to right. An interval is its pair of endpoints, and ∞ is none. Monotonicity is read cyclically (see the definition item).
Differences from the source:
- reading: the shortest path from one of these intervals to a singleton can be found using the standard breadth first search algorithm → for all d and I: I ∈ (layers δ X d).1 ↔ some word of length d leads a minimal interval to I under dPrimeFast, and every word that does has length ≥ d; reason: the claim about the standard algorithm is stated as the layer invariant of the layered search the goal runs, which is what yields the shortest path
- encoding: transitions of the interval automaton δ′ → the table-based evaluation dPrimeFast; reason: the algorithm evaluates δ′ through the preimage table; the preimage-test milestone shows dPrimeFast = dPrime1 for monotonic letters
- encoding: states s1, …, sn in cyclic order, letters σ1, …, σk, words in Σ∗ with δ(τ1τ2, s) = δ(τ2, δ(τ1, s)) → states Fin n with s_i = i − 1 and the cyclic order of Fin n, letters Fin k, words List (Fin k) read left to right (run = left fold); reason: relabelling; same instances
- encoding: interval [s_i, s_j] and the symbol ∞ → endpoint pair (i, j) : Fin n × Fin n with state set ivSet (i, j); ∞ is none in Option (Fin n × Fin n); reason: same objects; the n representations of S stay distinct pairs, as in the source
- generalization: the breadth-first search runs on the monotonic automaton of Theorem 1 (standing assumption of the section, p. 2) → no monotonicity hypothesis: the layer invariant is stated for every transition function δ; reason: the layer invariant is a property of the layered search alone; it specializes to the source's monotonic automata
import Mathlib import Definitions.Def_MonoReset_IntervalBFS_Model import Definitions.Def_MonoReset_IntervalBFS_Algorithm
namespace MonoReset.IntervalBFS
theorem bfs_layers {n k : ℕ} (δ : Fin k → Fin n → Fin n) (X : Finset (Fin n)) (d : ℕ)
(I : Fin n × Fin n) :
I ∈ (layers δ X d).1 ↔
(∃ τ : List (Fin k), τ.length = d ∧
∃ I₀ ∈ minIntervals X, τ.foldl (fun J a => dPrimeFast δ a J) (some I₀) = some I) ∧
∀ τ : List (Fin k),
(∃ I₀ ∈ minIntervals X, τ.foldl (fun J a => dPrimeFast δ a J) (some I₀) = some I) →
d ≤ τ.length := by sorry
end MonoReset.IntervalBFS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.