Contextual reasoning is NP-complete

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

The logic of context with the ist(c,p) modality has been proposed by McCarthy as a foundation for contextual reasoning. This paper shows that propositional logic of context is NP-complete and therefore more tractable than multimodal logics or Multi Language hierarchical logics which are PSPACE-complete. This result is given in a proof-theoretical way by providing a tableau calculus, which can be used as a decision procedure for automated reasoning. The computational gap between logic of context and modal logics is analyzed and some indications for the use of either formalisms are drawn on the basis of the tradeoff between compactness of representation and tractability of reasoning.
Original languageEnglish
Title of host publicationProceedings of the National Conference on Artificial Intelligence
PublisherAAAI
Pages621-626
Publication statusPublished - 1996
Externally publishedYes
EventProceedings of the 1996 13th National Conference on Artificial Intelligence, AAAI 96. Part 1 (of 2) -
Duration: 4 Aug 19968 Aug 1996

Publication series

NameProceedings of the National Conference on Artificial Intelligence

Conference

ConferenceProceedings of the 1996 13th National Conference on Artificial Intelligence, AAAI 96. Part 1 (of 2)
Period4/08/968/08/96

Fingerprint

Dive into the research topics of 'Contextual reasoning is NP-complete'. Together they form a unique fingerprint.

Cite this