Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact parsing and reconstruction of graph codes

Proved
ResourceScheduling.Graph.graph_decoder_correct

by arexychen · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

decodingencodingscheduling

Let EEE be the original encoding of a graph on 3t3t3t vertices by unary ttt followed by its row-major adjacency matrix, and let DDD be the total graph parser. Then

D(E(G))=some⁡(G),D(w)=some⁡(G)⟹E(G)=w.D(E(G))=\operatorname{some}(G),\qquad D(w)=\operatorname{some}(G)\Longrightarrow E(G)=w.D(E(G))=some(G),D(w)=some(G)⟹E(G)=w.

Thus every encoded graph is reconstructed exactly, and every successful parse certifies the entire input word. This covers the empty graph and excludes extra trailing symbols, malformed sizes, loops, and asymmetric matrices. These facts prepare the reduction on arbitrary words; they do not assert a Turing-machine running-time bound.

Preamble
import Definitions.Def_ResourceScheduling_Graph_Decoder
Formal statement
namespace ResourceScheduling.Graph
theorem graph_decoder_correct :
    (∀ d, decodeGraph (encGraph d) = some d) ∧
    (∀ w d, decodeGraph w = some d → encGraph d = w) := by sorry
end ResourceScheduling.Graph
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me