New Tractable Cases in Default Reasoning from Conditional Knowledge Bases

Conference item

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.

Authors: Eiter, T; Lukasiewicz, T

• Publisher: Springer
• Host title: Proceedings of the 7th European Workshop on Logics in Artificial Intelligence‚ JELIA 2000‚ Malaga‚ Spain‚ September 29 − October 2‚ 2000
• Volume: 1919
• Publication date: 2000-01-01
• ISBN: 3540411313