Correct decoding and unique factorization of unary codes
ProvedResourceScheduling.Graph.unary_codec_correctencodinginjectivityscheduling
Write for the mission's separator-terminated unary code. The parser reads a valid prefix with any suffix exactly, and every successful parse reconstructs the original word:
Furthermore, concatenation of unary codes is injective on finite lists of natural numbers. Thus a list of fields is uniquely determined by its serialized word. The empty natural-number list and zero-valued fields are included. These facts support parsing and malformed-input handling for encoded scheduling reductions.
Preamble
import Definitions.Def_ResourceScheduling_Graph_Codec
Formal statement
namespace ResourceScheduling.Graph
theorem unary_codec_correct :
(∀ n rest, readUnary (unary n ++ rest) = some (n, rest)) ∧
(∀ w n rest, readUnary w = some (n, rest) → w = unary n ++ rest) ∧
Function.Injective encNatList := by sorry
end ResourceScheduling.GraphSource
New elementary encoding lemma for the exact Prove2Me ResourceScheduling.Graph encodings (ResourceScheduling_Graph_Complexity, ResourceScheduling_Graph_GraphPartition, ResourceScheduling_Graph_ResDot11, ResourceScheduling_Graph_Construction). Construction: Blazewicz, Lenstra and Rinnooy Kan, Discrete Applied Mathematics 5 (1983), p. 15, Theorems 2-3, https://doi.org/10.1016/0166-218X(83)90012-4; author preprint https://ir.cwi.nl/pub/9642/9642D.pdf, printed pp. 5-6. The numerical encoding bound and parser lemmas are auxiliary results for the platform encoding, not numbered claims of the paper.