In previous work, we introduced a framework for the uniform formalization of families of non-classical logics with Kripke semantics, such as modal and relevance logics. Here we show how to use this framework to analyze the complexity of the decision problem for these logics, also in a uniform way. The result is a recipe: the user contributes bounds on structural reasoning and the accessibility relation associated with the Kripke semantics and the result is a decision procedure with bounded space requirements. As examples, we give PSPACE decision procedures for the modal logics K4 and S4, and for a positive fragment of the relevance logic B.

A Recipe for the Complexity Analysis of Non-Classical Logics

VIGANO', Luca
2000

Abstract

In previous work, we introduced a framework for the uniform formalization of families of non-classical logics with Kripke semantics, such as modal and relevance logics. Here we show how to use this framework to analyze the complexity of the decision problem for these logics, also in a uniform way. The result is a recipe: the user contributes bounds on structural reasoning and the accessibility relation associated with the Kripke semantics and the result is a decision procedure with bounded space requirements. As examples, we give PSPACE decision procedures for the modal logics K4 and S4, and for a positive fragment of the relevance logic B.
0863802524
9780863802522
Modal logics; complexity; non-classical logics
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11562/243774
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact