New Tractable Cases in Default Reasoning from Conditional Knowledge Bases

Abstract

We present new tractable cases for default reasoning from conditional knowledge bases. In detail, we introduce q-Horn conditional knowledge bases, which allow for a limited use of disjunction.We show that previous tractability results for epsilon-entailment, proper epsilon-entailment, and z- and z+-entailment in the Horn case can be extended to the q-Horn case. Moreover, we present feedback-free-Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. We show that the maximum entropy approach and lexicographic entailment are tractable in the feedback-free-Horn case. Our results complement and extend previous results, and contribute in refining the tractability / intractability frontier of default reasoning from conditional knowledge bases.