Default reasoning from conditional knowledge bases: Complexity and tractable cases

DOI10.1016/S0004-3702(00)00073-4zbMath0952.68139OpenAlexW2101013415MaRDI QIDQ1589638

Thomas Eiter, Thomas Lukasiewicz

Publication date: 12 December 2000

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(00)00073-4

zbMATH Keywords

computational complexitypolynomial-time algorithmsdefault reasoningnonmonotonic inferencereasoning under uncertaintyconditional knowledge basesHorn knowledge bases and variants

Mathematics Subject Classification ID

Knowledge representation (68T30) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Related Items (15)

Probabilistic logic under coherence: complexity and algorithms ⋮ 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 ⋮ Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation ⋮ Updating action domain descriptions ⋮ Defeasible inheritance with doubt index and its axiomatic characterization ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Weak nonmonotonic probabilistic logics ⋮ New tractable classes for default reasoning from conditional knowledge bases ⋮ Automated non-monotonic reasoning in System \textbf{P} ⋮ Belief functions and default reasoning ⋮ Compiling propositional weighted bases ⋮ Combining probabilistic logic programming with the power of maximum entropy

Uses Software

• Smodels

Cites Work

• Computing functions with parallel queries to NP
• Conditional entailment: bridging two approaches to default reasoning.
• Semantical considerations on nonmonotonic logic
• The complexity of optimization problems
• A first-order conditional logic for prototypical properties
• A logic for default reasoning
• Circumscription - a form of non-monotonic reasoning
• Non-monotonic logic. I
• On truth-table reducibility to SAT
• Nonmonotonic reasoning, preferential models and cumulative logics
• Hard problems for simple default logics
• Propositional knowledge base revision and minimal change
• On the consistency of defeasible databases
• What does a conditional knowledge base entail?
• On the complexity of propositional knowledge base revision, updates, and counterfactuals
• The complexity of model checking for circumscriptive formulae
• The logic of conditionals. An application of probability to deductive logic
• Nonmonotonic reasoning: From complexity to algorithms
• On first-order conditional logics
• The complexity of propositional closed world reasoning and circumscription
• A taxonomy of complexity classes of functions
• Unifying default reasoning and belief revision in a modal framework
• Conditional logics of normality: A modal approach
• Recognition of \(q\)-Horn formulae in linear time
• Polynomial-time inference of all valid implications for Horn and related formulae
• Abduction from logic programs: Semantics and complexity
• Nonmonotonic reasoning, conditional objects and possibility theory
• The complexity of belief update
• Belief functions and default reasoning
• Computing with default logic
• Another perspective on default reasoning
• Qualitative probabilities for default reasoning, belief revision, and causal modeling
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• From statistical knowledge bases to degrees of belief
• Bounded Query Classes
• On the logic of theory change: Partial meet contraction and revision functions
• Nonmonotonic Logic II
• Complexity Results for Nonmonotonic Logics
• Mixed integer programming methods for computing nonmonotonic deductive databases
• The complexity of logic-based abduction
• Conditional objects as nonmonotonic consequence relationships
• Plausibility measures and default reasoning
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Default reasoning from conditional knowledge bases: Complexity and tractable cases