New Tractable Cases in Default Reasoning from Conditional Knowledge Bases
Thomas Eiter and Thomas Lukasiewicz
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.