We present a new proof-theoretic approach to bounding the complexity of the decision problem for propositional modal logics. We formalize logics in a uniform way as sequent systems and then restrict the structural rules for particular systems. This, combined with an analysis of the accessibility relation of the corresponding Kripke structures, yields decision procedures with bounded space requirements. As examples we give O(n log n) space procedures for the modal logics K and T.

A New Method for Bounding the Complexity of Modal Logics

VIGANO', Luca
1997

Abstract

We present a new proof-theoretic approach to bounding the complexity of the decision problem for propositional modal logics. We formalize logics in a uniform way as sequent systems and then restrict the structural rules for particular systems. This, combined with an analysis of the accessibility relation of the corresponding Kripke structures, yields decision procedures with bounded space requirements. As examples we give O(n log n) space procedures for the modal logics K and T.
3540633855
Modal logics; proof theory; complexity
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/243776
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact