The fused single-pass evaluation scan equals the decoding-based semantics
ProvedCookLevin.evalScan_charFor the unary-encoded CNF strings of the Cook-Levin encoding, the fused single-pass evaluation scan of the string x under the certificate bits w coincides with the standard decoding-based semantics. Writing decodeFormula(x) for the greedily decoded CNF formula, a positive literal Pos n reads bit n of the certificate w (with out-of-range bits equal to false) and a negative literal Neg n reads its negation; the scan verdict equals the conjunction over all decoded clauses of the disjunction over their literals. The theorem asserts that the automaton scanAux, which threads a control mode, a clause accumulator, a formula accumulator and a unary counter in one left-to-right pass and closes pending literals and clauses on the empty string, computes exactly this decoded semantics for every string, including strings that end mid-list.
import Definitions.Def_CookLevin_evalScan
namespace CookLevin
theorem evalScan_char (x w : List Bool) :
evalScan x w =
(decodeFormula x).all (fun clause =>
clause.any (fun lit => match lit with
| Literal.Neg n => !(w.getD n false)
| Literal.Pos n => w.getD n false)) := by sorry
end CookLevin