The Complexity of Model Checking for Propositional Default Logics

Data and Knowledge Engineering

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: Reiter's, justified, constrained, rational, and cumulative. We prove that all the analyzed variants are Sigma2-complete in the general case, and remains so even if all defaults are prerequisite-free and seminormal. Cumulative default logic is also Sigma2-complete even if all defaults are normal and prerequisite-free. The other semantics are Delta-log2-complete and coNP-complete if all defaults are normal and prerequisites are allowed or not, respectively.

 @article{libe-scha-06-b,
 title = {The Complexity of Model Checking for Propositional Default Logics},
 year = {2005},
 author = {Liberatore, Paolo and Schaerf, Marco},
 journal = {Data and Knowledge Engineering},
 pages = {189-202},
 number = {2},
 volume = {55},
 }