Focusing [1] is a proof-theoretic device to structure proof search in the sequent calculus: it provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured in two separate and disjoint phases. It is commonly believed that every “reasonable” sequent calculus has a natural focused version. Although stemming from proof-search considerations, focusing has not been thoroughly investigated in actual theorem proving, in particular w.r.t. termination, if not for the folk observations that only negative formulas need to be duplicated (or contracted if seen from the top down) in the focusing phase. We present a contraction-free (and hence terminating) focused proof system for multi-succedent propositional intuitionistic logic, which refines the G4ip calculus of Vorob’ev, Hudelmeier and Dyckhoff. We prove the completeness of the approach semantically and argue that this offers a viable alternative to other more syntactical means.

Focusing on contraction / A. Avellone, C. Fiorentini, A. Momigliano - In: Proceedings of the 28th Italian conference on computational logic (CILC 2013) : Catania, Italy, september 25-27, 2013. / [a cura di] D. Cantone, M.N. Asmundo. - Aachen : CEUR, 2013. - pp. 65-81 (( Intervento presentato al 28. convegno Italian conference on computational logic (CILC) tenutosi a Catania nel 2013.

Focusing on contraction

C. Fiorentini;A. Momigliano
2013

Abstract

Focusing [1] is a proof-theoretic device to structure proof search in the sequent calculus: it provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured in two separate and disjoint phases. It is commonly believed that every “reasonable” sequent calculus has a natural focused version. Although stemming from proof-search considerations, focusing has not been thoroughly investigated in actual theorem proving, in particular w.r.t. termination, if not for the folk observations that only negative formulas need to be duplicated (or contracted if seen from the top down) in the focusing phase. We present a contraction-free (and hence terminating) focused proof system for multi-succedent propositional intuitionistic logic, which refines the G4ip calculus of Vorob’ev, Hudelmeier and Dyckhoff. We prove the completeness of the approach semantically and argue that this offers a viable alternative to other more syntactical means.
Settore INF/01 - Informatica
Settore MAT/01 - Logica Matematica
http://ceur-ws.org/Vol-1068/paper-l05.pdf
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
2013_cilc.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 552 kB
Formato Adobe PDF
552 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/227228
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact