English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  A New Method for Bounding the Complexity of Modal Logics

Basin, D. A., Matthews, S., & Viganò, L. (1997). A New Method for Bounding the Complexity of Modal Logics. In G. Gottlob, A. Leitsch, & D. Mundici (Eds.), Proceedings of the 5th Kurt Gödel Colloquium on Computational Logic and Proof Theory (KGC-97) (pp. 89-102). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Basin, David A.1, Author           
Matthews, Seán1, Author           
Viganò, Luca1, Author           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 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) procedures for the modal logics K and T.

Details

show
hide
Language(s): eng - English
 Dates: 2010-11-291997
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 519474
Other: Local-ID: C1256104005ECAFC-177C685B217C327FC1256484004F78B1-Basin97d
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Vienna, Austria
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 5th Kurt Gödel Colloquium on Computational Logic and Proof Theory (KGC-97)
Source Genre: Proceedings
 Creator(s):
Gottlob, G., Editor
Leitsch, A., Editor
Mundici, D., Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 89 - 102 Identifier: ISBN: 3-540-63385-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1289 Sequence Number: - Start / End Page: - Identifier: -