Projects
researchIn development

DLDS / Lean

Formal verification of dag-like derivability structures, local proof checking, and Boolean circuits in Lean 4.

Platform
Source
Role
Researcher · PUC-Rio
Built with
Lean 4Mathlib
First page of From Dag-Like Proofs to Boolean Circuits in Lean.First page of Quantum Verification of Compressed Proofs through DLDS-to-Circuit Compilation.

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.

Publications

Comments 0