AFTD Auto-Formalizing Theoretical Domains

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]
See it in the graphDiscuss this resultChallenge it