Lemma 5.2 (Safety of the compiler): every compiled scheme is safe
ProvedTreeEquivalenceHORS.Equivalence.lemma_5_2higher-order-recursion-schemesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1safety
For every two-counter program and side , the compiled scheme is safe in the sense of Section 3: all nonterminal and body-subterm types are homogeneous, and every application operand satisfies for every rule parameter occurring in .
Safety of the compiler output is what places the lower bound in the safe class.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence /-- **Lemma 5.2 (Safety of the compiler)** (printed p. 16 / PDF p. 18). For every `M` and side `⋄`, the compiled scheme `G^⋄_M` is safe. -/ theorem lemma_5_2 (M : Machine) (side : Side) : (compile side M).Safe := by sorry end TreeEquivalenceHORS.Equivalence
Source
Mingkun Xiao, Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, STOC 2027 submission #421 (October 2026), source.pdf SHA-256 e875d09ced029e3f5cb114abba049e4a2b1bdaa9b064c98b0d71f2ec7451c7af, Lemma 5.2, printed p. 16 / PDF p. 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.