op75_parse_subset_aux_complete
theoremverified
Sufficient fuel makes the parser accept every canonical instance and return its weights and target.
Statement
theorem op75_parse_subset_aux_complete (as : List ℕ) (t : ℕ) (fuel : ℕ)
(hf : as.length < fuel) :
op75_parse_subset_aux fuel (op75_subset_encoding as t) = some (as, t)- Source
- OP-75: canonical subset-sum input decoder for the width-three ReLU compiler.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- op75_parse_subset_auxA total fuel-bounded decoder for canonical subset-sum instances.
- op75_parse_nat_completeThe parser accepts every canonical natural encoding with an arbitrary suffix and returns the value, suffix and correct nonzero flag.
- op75_subset_encoding_consEncoding a nonempty weight list emits its marker, the head natural, then the remaining instance.
- op75_subset_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
- relu_encode_natBinary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true…
- op75_parse_natDecode one canonical self-delimiting binary natural, returning its value, the unconsumed suffix, and whether the value is nonzero; reject…
- Used by 1
- op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.
Lean source view module on GitHub
theorem op75_parse_subset_aux_complete (as : List ℕ) (t : ℕ) (fuel : ℕ) (hf : as.length < fuel) : op75_parse_subset_aux fuel (op75_subset_encoding as t) = some (as, t) := by induction as generalizing fuel with | nil => cases fuel with | zero => simp at hf | succ fuel => have he := op75_parse_nat_complete t [] simp only [List.append_nil] at he simp [op75_subset_encoding, op75_parse_subset_aux, he] | cons a as ih => cases fuel with | zero => simp at hf | succ fuel => have hs : as.length < fuel := by simp at hf; omega rw [op75_subset_encoding_cons] simp only [op75_parse_subset_aux, op75_parse_nat_complete] rw [ih fuel hs]