@inproceedings{067b517569df4608a0fe6439a7bab2b5,

title = "Contextual reasoning is NP-complete",

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.",

author = "Fabio Massacci",

year = "1996",

language = "English",

series = "Proceedings of the National Conference on Artificial Intelligence",

publisher = "AAAI",

pages = "621--626",

booktitle = "Proceedings of the National Conference on Artificial Intelligence",

note = "Proceedings of the 1996 13th National Conference on Artificial Intelligence, AAAI 96. Part 1 (of 2) ; Conference date: 04-08-1996 Through 08-08-1996",

}