Computer Science – Artificial Intelligence
Scientific paper
2011-05-27
Journal Of Artificial Intelligence Research, Volume 9, pages 423-461, 1998
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.554
In default reasoning, usually not all possible ways of resolving conflicts between default rules are acceptable. Criteria expressing acceptable ways of resolving the conflicts may be hardwired in the inference mechanism, for example specificity in inheritance reasoning can be handled this way, or they may be given abstractly as an ordering on the default rules. In this article we investigate formalizations of the latter approach in Reiter's default logic. Our goal is to analyze and compare the computational properties of three such formalizations in terms of their computational complexity: the prioritized default logics of Baader and Hollunder, and Brewka, and a prioritized default logic that is based on lexicographic comparison. The analysis locates the propositional variants of these logics on the second and third levels of the polynomial hierarchy, and identifies the boundary between tractable and intractable inference for restricted classes of prioritized default theories.
No associations
LandOfFree
Complexity of Prioritized Default Logics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Prioritized Default Logics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Prioritized Default Logics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664456