Skip to Main content Skip to Navigation
Book sections

Coinductive Proof Search for Polarized Logic with Applications to Full Intuitionistic Propositional Logic

Abstract : The approach to proof search dubbed "coinductive proof search", and previously developed by the authors for implicational intuitionistic logic, is in this paper extended to LJP , a focused sequent-calculus presentation of polarized intuitionistic logic, including an array of positive and negative connectives. As before, this includes developing a coinductive description of the search space generated by a sequent, an equivalent inductive syntax describing the same space, and decision procedures for inhabitation problems in the form of predicates defined by recursion on the inductive syntax. We prove the decidability of existence of focused inhabitants, and of finiteness of the number of focused inhabitants for polarized intuitionistic logic, by means of such recursive procedures. Moreover, the polarized logic can be used as a platform from which proof search for other logics is understood. We illustrate the technique with LJT , a focused sequent calculus for full intuitionistic propositional logic (including disjunction). For that, we have to work out the "negative translation" of LJT into LJP (that sees all intuitionistic types as negative types), and verify that the translation gives a faithful representation of proof search in LJT as proof search in the polarized logic. We therefore inherit decidability of both problems studied for LJP and thus get new proofs of these results for LJT .
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03255968
Contributor : Ralph Matthes Connect in order to contact the contributor
Submitted on : Wednesday, June 9, 2021 - 11:14:20 PM
Last modification on : Tuesday, October 19, 2021 - 2:23:31 PM
Long-term archiving on: : Friday, September 10, 2021 - 7:27:36 PM

File

LIPIcs-TYPES-2020-4.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

José Espírito Santo, Ralph Matthes, Luís Pinto. Coinductive Proof Search for Polarized Logic with Applications to Full Intuitionistic Propositional Logic. Ugo de'Liguoro; Stefano Berardi; Thorsten Altenkirch. LIPIcs : 26th International Conference on Types for Proofs and Programs (TYPES 2020), 188, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2021, LIPIcs : Leibniz International Proceedings in Informatics ; ISSN : 1868-8969, 978-3-95977-182-5. ⟨10.4230/LIPIcs.TYPES.2020.4⟩. ⟨hal-03255968⟩

Share

Metrics

Record views

50

Files downloads

21