Overview
A traditional natural deduction proof is a tree. Horizontal compression shares repeated structure, producing a dag-like derivability structure, or DLDS. The research asks how to verify these compressed objects through local, independently checkable conditions.
This Lean 4 development works with purely implicational minimal logic. It defines validity, connects the validity predicate to proof readings and local certificates, and studies how checks can be expressed as circuits.
Formalization
- A validity predicate for a DLDS and its relationship to natural deduction.
- Local certificate checking and executable checks.
- Proof search and bounded certificate sizes.
- Applications to certificates of non-Hamiltonicity.
- Reversible circuits for checking failures, with correctness statements in Lean.
The public repository’s ReleaseSurface.lean lists the main results as #check statements. Its README explains the exact scope and trust assumptions, including the distinction between general theorems and concrete instances that use native_decide.
Scope
The compression theorem of Gordeev and Haeusler and the BBHT quantum search algorithm are cited in the development; they are not themselves formalized there.
The LSFA paper establishes pointwise correctness of the Boolean circuit evaluator and a bridge for the simple-tree fragment. The SBCCQ paper studies reversible quantum oracles for a restricted deferred-discharge regime, with Qiskit simulations. Their stated results are distinct from the broader ongoing Lean development.
Research context
Author: Lorenzo Saraiva, PUC-Rio. Advisor: Edward Hermann Haeusler. The repository contains the formal statements, pinned Lean toolchain, and build instructions.
Publication records: LSFA 2026 · SBCCQ 2026.


Comments 0