Designing a Safe Forward Chaining Tactic Using Productive Proofs
Open Access
- 25 September 2025
- book chapter
- Published by Springer Nature
- p. 299-317
Abstract
We present a proof-theoretic treatment of forward chaining and saturation within a multisorted, first-order intuitionistic logic with equality. The notions of polarity and focused proofs are central to our approach since they provide a characterization of geometric implications as bipolar formulas as well as a natural setting to describe forward chaining and the concept of productive proofs. We identify conditions under which forward chaining with a given set of formulas is guaranteed to saturate in a finite number of steps. The motivation for this research stems, in part, from exploring avenues to automate the Abella theorem prover, which relies on relational specifications, and where theorems in typical proof developments are essentially bipolar formulas. We illustrate the potential benefits of automating forward chaining and saturation for Abella by presenting examples that compute congruence closure and assist in other equational and relational reasoning tasks.Keywords
This publication has 23 references indexed in Scilit:
- From axioms to synthetic inference rules via focusingAnnals of Pure and Applied Logic, 2022
- Proof Pearl: Abella Formalization of λ-Calculus Cube Property2012
- Nominal abstractionInformation and Computation, 2011
- Focusing and polarization in linear, intuitionistic, and classical logicsTheoretical Computer Science, 2009
- Canonical Sequent Proofs via Multi-Focusing2008
- A Logical Characterization of Forward and Backward Chaining in the Inverse MethodJournal of Automated Reasoning, 2008
- Contraction-free sequent calculi for geometric theories with an application to Barr's theoremArchive for Mathematical Logic, 2003
- Labelled Non-Classical Logics2000
- A basis for deductive database systems IIThe Journal of Logic Programming, 1986
- Untersuchungen ber das logische Schlie en. IMathematische Zeitschrift, 1935