Verified and Optimized Implementation of Orthologic Proof Search

Simon Guilloud and Clément Pit-Claudel · 2025

Read Verified and Optimized Implementation of Orthologic Proof Search by Simon Guilloud and Clément Pit-Claudel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09418.txt.

Introduction

Simon Guilloud and Clément Pit-Claudel deliver a proof search tool for orthologic that is both verified and fast. Their twenty twenty-five paper concerns a logic weaker than classical logic, used as a safe, quick stand-in inside automated reasoners. Trust matters: a wrong prover poisons every check built on it.

The full system is formalized in the Coq proof assistant, with soundness and completeness proven. Formalizing cut elimination exposed a missing case in a published proof, now fixed. Memo tricks bring the search to quadratic time. A reflective tactic lets Coq users call the prover and bank its verdict as a machine-checked fact.

Catalog record

CREATORSimon Guilloud and Clément Pit-Claudel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-09418

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Verified and Optimized Implementation of Orthologic Proof Search Simon Guilloud and Clément Pit-Claudel Abstract We report on the development of an optimized and verified decision procedure for orthologic equalities and inequalities. This decision procedure is quadratic-time and is used as a sound, efficient and predictable approximation to classical propositional logic in automated reasoning tools. We formalize, in the Coq proof assistant, a proof system in sequent-calculus style for orthologic. We then prove its soundness and completeness with respect to the algebraic variety of ortholattices, and we formalize a cut-elimination theorem (in doing so, we discover and fix a missing case in a previously published proof). We then implement and verify a complete proof search procedure for orthologic. A naive implementation is exponential, and to obtain an optimal quadratic runtime, we optimize the implementation by memoizing its results and simulating reference equality testing. We leverage the resulting correctness theorem to implement a reflective Coq tactic. We present benchmarks showing the procedure, under various optimizations, matches its theoretical complexity. Finally, we develop tactics including normalization with respect to orthologic and a boolean solver, which we also benchmark. We make tactics available as a standalone Coq plugin. \lst@InputCatcodes \lst@RestoreCatcodes 1 Introduction Specialized, reliable and efficient building blocks are indispensable in scaling automated reasoning software. Program verifiers, SMT solvers, proof assistants and automated theorem provers use them to tackle the various theories and subproblems that compounds a logical statement. As they combine, so do the possibility of an implementation error. To ensure that they can be used as trusted components in program verification pipelines, it is very desirable to verify these verification algorithms themselves. One fragment of particular interest is propositional logic. Despite significant progress in SAT solvers, solving satisfiability or validity of propositional formulas remains a major challenge to scalability of decision procedures. An alternative and complementary approach to heuristics is orthologic-based reasoning. Orthologic is a non-distributive generalization of classical propositional logic which admits polynomial-time ( \mathcal{O}(n^{2}) ) validity checking and normalization algorithms [ 3 , 8 , 11 ] . Orthologic offers a trade-off: it sacrifices completeness (with respect to classical semantics) in exchange for guaranteed efficiency and predictability. It also admits a quadratic-time normalization algorithm, allowing to compute a unique normal form (with respect to the laws of orthologic) of guaranteed minimal size. This helps with caching, solves a variety of intuitive formula equivalences, and allows simplifying formulas before solving them with more complete but possibly inefficient procedures. Recent work has demonstrated the practical utility of orthologic-based reasoning, being an important component of verification tools such as the Stainless program verifier [ 8 ] and the Lisa proof assistant [ 9 ] . Table 1 presents the laws of orthologic. V1: x\lor y=y\lor x V1’: x\land y=y\land x V2: x\lor(y\lor z)=(x\lor y)\lor z V2’: x\land(y\land z)=(x\land y)\land z V3: x\lor x=x V3’: x\land x=x V4: x\lor 1=1 V4’: x\land 0=0 V5: x\lor 0=x V5’: x\land 1=x V6: \neg\neg x=x V7: x\lor\neg x=1 V7’: x\land\neg x=0 V8: \neg(x\lor y)=\neg x\land\neg y V8’: \neg(x\land y)=\neg x\lor\neg y V9: x\lor(x\land y)=x V9’: x\land(x\lor y)=x Table 1: Laws of ortholattices, algebraic varieties with signature (S,\land,\lor,0,1,\neg) . In this work, we present the first formalization and verification, using the Coq proof assistant, of an efficient decision procedure for the validity and equivalence problems for propositional formulas in orthologic. This algorithm [ 11 ] is based on proof search in a proof system for orthologic that is a restriction of the classical sequent calculus where a sequent can never contain more than two distinct formulas at a time. Despite this restriction, the proof system admits cut elimination, which we formalize. The cut elimination property implies a subformula property, which is key to the completeness of the proof search procedure. A naive implementation of the decision procedure has exponential complexity. To obtain a polynomial version, we leverage memoization, i.e. storing in a table the intermediate results of the recursive calls. Moreover, using structural equality to check if a key is in the memoization map costs an additional linear runtime factor. To obtain an optimal quadratic version, we modify the algorithm to use a form of reference equality. As our algorithm is purely functional, this means we have to extend our formulas abstract syntax trees to assign to each node a unique identifier (or pointer) that can then be used in the memoization map. We formally prove the correctness of these constructions. We implement and verify multiple versions of the algorithm: without optimization ( \widetilde{\mathcal{O}}(2^{n}) ), with memoization using lists ( \widetilde{\mathcal{O}}(n^{5}) ), using AVL maps ( \widetilde{\mathcal{O}}(n^{3}) ), and using AVL maps and simulated reference equality ( \widetilde{\mathcal{O}}(n^{2}) ). Memoization and reference equality are generic, and important in many tools and algorithms. Our approach to verifying these optimizations is not specific to orthologic proof search and we expect it to extend to any recursive algorithms over algebraic data types. Using the technique of proofs by reflection, we then obtain a set of executable proof tactics that decides equality modulo orthologic rule and which is applicable to any ortholattice, in particular the type bool of boolean values. This tactic is able to solve automatically, for example, ⬇ true = ( a && b ) || ( negb a ) || ( negb b ) . We present benchmarks attesting that each version of the proof search procedure (with memoization using a list-based map, with memoization using AVL trees, and with both memoization and reference equality) meets the theoretical complexity. Many formulas are not completely provable in the fragment of orthologic, in which case the decision procedure alone cannot do anything, even if most of the structure of the formula reduces under orthologic rules. The orthologic simplification algorithm [ 8 ] on the other hand is widely applicable, and can make substantial progress on a problem even if the formula is not equivalent to true. This is also very useful if the propositional formulas are built on some theories, such as arithmetic, in which case even classical boolean decision procedures would not work. We implement this simplifier in OCaml as a Coq plugin, using the above tactic to efficiently prove equivalence with the original expression. This yields a generic simplification tactic for terms of type bool . We finally leverage this normalization tactic to implement a boolean solver which alternates between branching on a variable and normalizing the formulas, as in [ 9 ] . We present benchmarks comparing this procedure to the built-in btauto tactic. All our tactics are available as a Coq plugin alongside with benchmarks at [redacted]. 1.1 Contributions In section 2 , we first formalize in the Coq proof assistant a proof system for orthologic (in the style of sequent calculus) and its soundness and completeness with respects to truth in every ortholattice. In section 3 , we then formalize the cut elimination theorem (without non-logical axioms) of orthologic, and in the process discover a missing edge case in the proof of [ 11 ] . In section 4 , we implement the proof-search based decision procedure for orthologic from [ 11 ] . We prove soundness and completeness of the algorithm. We then use reflection to obtain a Coq proof tactic which can solve any

Read the complete text