The Complexity of Model Checking for Propositional Default Logics

Paolo Liberatore and Marco Schaerf

Proceedings of the Thirteenth European Conference on Artificial Intelligence (ECAI'98)

Default logic is one of the most widely used formalisms to formalize commonsense reasoning. In this paper we analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature. We prove that all the analyzed variants have the same complexity and that this problem is in general Sigma2 complete, while it is CoNP complete under some restrictions on the form of the defaults.


 @inproceedings{libe-scha-98,
 title = {The Complexity of Model Checking for Propositional Default Logics},
 year = {1998},
 author = {Liberatore, Paolo and Schaerf, Marco},
 booktitle = {Proceedings of the Thirteenth European Conference on Artificial
 Intelligence (ECAI'98)},
 pages = {18-22},
 publisher = {John Wiley Press},
 }
 
HTTP download.
FTP download.