op75_parse_subset_spec
theoremverified
The total decoder returns a weight list and target exactly when their canonical encoding equals its input.
Statement
theorem op75_parse_subset_spec (w : List Bool) (as : List ℕ) (t : ℕ) :
op75_parse_subset 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 5
- op75_parse_subsetDecode a canonical subset-sum bit string, rejecting malformed or trailing data.
- op75_parse_subset_aux_soundEvery successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.
- op75_parse_subset_aux_completeSufficient fuel makes the parser accept every canonical instance and return its weights and target.
- op75_subset_encoding_length_lowerThe number of weights is at most the bit length of the encoded 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…
- Used by 1
- op75_subset_compiler_function_correctThe explicit total compiler preserves language membership.
Lean source view module on GitHub
theorem op75_parse_subset_spec (w : List Bool) (as : List ℕ) (t : ℕ) : op75_parse_subset w = some (as, t) ↔ op75_subset_encoding as t = w := by constructor · intro h exact op75_parse_subset_aux_sound (w.length+1) w as t h · intro h subst w unfold op75_parse_subset apply op75_parse_subset_aux_complete have hs := op75_subset_encoding_length_lower as t omega