AFTD Auto-Formalizing Theoretical Domains

op75_parse_subset_aux_sound

theoremverified

Every successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.

Statement

theorem op75_parse_subset_aux_sound (fuel : ℕ) (w : List Bool) (as : List ℕ) (t : ℕ)
    (h : op75_parse_subset_aux fuel w = some (as, t)) : op75_subset_encoding as t = w
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_soundEvery successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.
  • op75_subset_encoding_consEncoding a nonempty weight list emits its marker, the head natural, then the remaining instance.
  • 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…
  • op75_subset_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
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_sound (fuel : ℕ) (w : List Bool) (as : List ℕ) (t : ℕ)
    (h : op75_parse_subset_aux fuel w = some (as, t)) : op75_subset_encoding as t = w := by
  induction fuel generalizing w as t with
  | zero => simp [op75_parse_subset_aux] at h
  | succ fuel ih =>
      cases w with
      | nil => simp [op75_parse_subset_aux] at h
      | cons mark tail =>
          cases mark with
          | false =>
              cases hp : op75_parse_nat tail with
              | none => simp [op75_parse_subset_aux, hp] at h
              | some value =>
                  rcases value with ⟨n, rest, nz⟩
                  cases rest with
                  | nil =>
                      simp [op75_parse_subset_aux, hp] at h
                      obtain ⟨rfl, rfl⟩ := h
                      have hs := (op75_parse_nat_sound tail n [] nz hp).1
                      simpa [op75_subset_encoding] using congrArg (List.cons false) hs.symm
                  | cons b rest => simp [op75_parse_subset_aux, hp] at h
          | true =>
              cases hp : op75_parse_nat tail with
              | none => simp [op75_parse_subset_aux, hp] at h
              | some value =>
                  rcases value with ⟨a, rest, nz⟩
                  cases hq : op75_parse_subset_aux fuel rest with
                  | none => simp [op75_parse_subset_aux, hp, hq] at h
                  | some value =>
                      rcases value with ⟨bs, u⟩
                      simp [op75_parse_subset_aux, hp, hq] at h
                      obtain ⟨rfl, rfl⟩ := h
                      have hs := (op75_parse_nat_sound tail a rest nz hp).1
                      have hr := ih rest bs u hq
                      rw [op75_subset_encoding_cons, hr, ← hs]
See it in the graphDiscuss this resultChallenge it