Complexity results for 2CNF default theories

• Autorzy: Zhao X. , Ding D.
• Języki publikacji: EN

Abstrakty

EN

This paper is concerned with the complexity of default reasoning with 2CNF default theories (D,W) in which W is a set of literals and D is a set of 2CNF defaults. It is proved that the problem whether a literal occurs in at least one extension can be solved in polynomial time. But the problem whether a literal appears in all extensions is proved to be co-NP-complete. The complexity of some subclasses of 2CNF default theories is also analyzed.

Słowa kluczowe

EN

2CNF default theory; credulous reasoning; skeptical reasoning; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 45, nr 4
• Strony: 393--404
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

Zhao X.

autor

Ding D.

• Department of Mathematics Henan Normal University Xinxiang, 453002, P.R.China,