n this article we study the complexity of disjunction property for intuitionistic logic, the modal logics S4, S4.1, Grzegorczyk logic, Godel-Lob logic, and the intuitionistic counterpart of the modal logic K. For S4 we even prove the feasible interpolation theorem and we provide a lower bound for the length of proofs. The techniques we use do not require proving structural properties of the calculi in hand, such as the cut-elimination theorem or the normalization theorem. This is a key point of our approach, since it allows us to treat logics for which only Hilbert-style characterizations are known

On the complexity of the disjunction property in intuitionistic and modal logics

FERRARI, MAURO;
2005

Abstract

n this article we study the complexity of disjunction property for intuitionistic logic, the modal logics S4, S4.1, Grzegorczyk logic, Godel-Lob logic, and the intuitionistic counterpart of the modal logic K. For S4 we even prove the feasible interpolation theorem and we provide a lower bound for the length of proofs. The techniques we use do not require proving structural properties of the calculi in hand, such as the cut-elimination theorem or the normalization theorem. This is a key point of our approach, since it allows us to treat logics for which only Hilbert-style characterizations are known
disjunction property complexity; intuitionistic logic; feasible interpolation theorem; calculi; cut-elimination theorem; normalization theorem; Hilbert-style characterization; S4 modal logic; S4.1 modal logic; Grzegorczyk logic; Godel-Lob logic
File in questo prodotto:
File Dimensione Formato  
tocl-2005.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 169.09 kB
Formato Adobe PDF
169.09 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11383/1504070
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact