Default reasoning from conditional knowledge bases: Complexity and tractable cases
Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form ``\(\phi \rightarrow \psi\), which informally read as ``generally, if \(\phi\) then \(\psi\). Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base \(KB\) and a default \(\phi \rightarrow \psi\), does \(KB\) entail \(\phi \rightarrow \psi\)? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to \(q\)-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.
- A first-order conditional logic for prototypical properties
- A logic for default reasoning
- A taxonomy of complexity classes of functions
- Abduction from logic programs: Semantics and complexity
- Another perspective on default reasoning
- Belief functions and default reasoning
- Bounded Query Classes
- Circumscription - a form of non-monotonic reasoning
- Complexity Results for Nonmonotonic Logics
- Computing functions with parallel queries to NP
- Computing with default logic
- Conditional entailment: bridging two approaches to default reasoning.
- Conditional logics of normality: A modal approach
- Conditional objects as nonmonotonic consequence relationships
- From statistical knowledge bases to degrees of belief
- Hard problems for simple default logics
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 4152345 (Why is no real title available?)
- scientific article; zbMATH DE number 4166940 (Why is no real title available?)
- scientific article; zbMATH DE number 67496 (Why is no real title available?)
- scientific article; zbMATH DE number 97792 (Why is no real title available?)
- scientific article; zbMATH DE number 140400 (Why is no real title available?)
- scientific article; zbMATH DE number 140406 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1198947 (Why is no real title available?)
- scientific article; zbMATH DE number 1269566 (Why is no real title available?)
- scientific article; zbMATH DE number 1301756 (Why is no real title available?)
- scientific article; zbMATH DE number 478394 (Why is no real title available?)
- scientific article; zbMATH DE number 592370 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 754675 (Why is no real title available?)
- scientific article; zbMATH DE number 1453052 (Why is no real title available?)
- Mixed integer programming methods for computing nonmonotonic deductive databases
- Non-monotonic logic. I
- Nonmonotonic Logic II
- Nonmonotonic reasoning, conditional objects and possibility theory
- Nonmonotonic reasoning, preferential models and cumulative logics
- Nonmonotonic reasoning: From complexity to algorithms
- On first-order conditional logics
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- On the consistency of defeasible databases
- On the logic of theory change: Partial meet contraction and revision functions
- On truth-table reducibility to SAT
- Plausibility measures and default reasoning
- Polynomial-time inference of all valid implications for Horn and related formulae
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Propositional knowledge base revision and minimal change
- Qualitative probabilities for default reasoning, belief revision, and causal modeling
- Recognition of q-Horn formulae in linear time
- Semantical considerations on nonmonotonic logic
- The complexity of belief update
- The complexity of logic-based abduction
- The complexity of model checking for circumscriptive formulae
- The complexity of optimization problems
- The complexity of propositional closed world reasoning and circumscription
- The logic of conditionals. An application of probability to deductive logic
- Unifying default reasoning and belief revision in a modal framework
- What does a conditional knowledge base entail?
- Fixed-parameter tractability of disjunction-free default reasoning
- Belief functions and default reasoning
- Connections between default reasoning and partial constraint satisfaction
- Automated non-monotonic reasoning in System \textbf{P}
- Default consequence relations from topology and measure theory
- Expressive probabilistic description logics
- In all but finitely many possible worlds: model-theoretic investigations on `\textit{overwhelming majority}' default conditionals
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- Weak nonmonotonic probabilistic logics
- New tractable classes for default reasoning from conditional knowledge bases
- scientific article; zbMATH DE number 2014711 (Why is no real title available?)
- scientific article; zbMATH DE number 1759386 (Why is no real title available?)
- Using approximate reasoning to represent default knowledge
- Stability, vertex stability, and unfrozenness for special graph classes
- Updating action domain descriptions
- Defeasible inheritance with doubt index and its axiomatic characterization
- Defeasible RDFS via rational closure
- Compiling propositional weighted bases
- Combining probabilistic logic programming with the power of maximum entropy
- Probabilistic logic under coherence: complexity and algorithms
- Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation
This page was built for publication: Default reasoning from conditional knowledge bases: Complexity and tractable cases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589638)
