Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10321210 | Data & Knowledge Engineering | 2005 | 14 Pages |
Abstract
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 Σ2p-complete in the general case, and remains so even if all defaults are prerequisite-free and seminormal. Cumulative default logic is also Σ2p-complete even if all defaults are normal and prerequisite-free. The other semantics are Î2p[logn]-complete and coNP-complete if all defaults are normal and prerequisites are allowed or not, respectively.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Paolo Liberatore, Marco Schaerf,