New tractable classes for default reasoning from conditional knowledge bases
This paper refines the tractability/intractability frontier of default reasoning from conditional knowledge bases. It presents two new tractable cases with relation to lexicographic entailment. In particular, we have introduced nested conditional knowledge bases and co-nested conditional knowledge bases, which are meaningful conditional knowledge bases. Both tractable classes presented in this paper can be recognized in linear time.
tractable classes lexicographic semantic non-monotonic reasoning