Abduction from logic programs: Semantics and complexity

DOI10.1016/S0304-3975(96)00179-XzbMath0893.68022MaRDI QIDQ1389684

Nicola Leone, Thomas Eiter, Georg Gottlob

Publication date: 30 June 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

knowledge representationreasoning

Mathematics Subject Classification ID

Logic programming (68N17)

Related Items (23)

Hypothesizing about signaling networks ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Inconsistency Management for Traffic Regulations: Formalization and Complexity Results ⋮ The View-Update Problem for Indefinite Databases ⋮ What makes propositional abduction tractable ⋮ Outlier detection using default reasoning ⋮ A Measure of Arbitrariness in Abductive Explanations ⋮ From causes for database queries to repairs and model-based diagnosis and back ⋮ Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints ⋮ A general framework for preferences in answer set programming ⋮ The power of non-ground rules in Answer Set Programming ⋮ On the complexity of second-best abductive explanations ⋮ Inference to the stable explanations ⋮ Brave induction: a logical framework for learning from incomplete information ⋮ Brave Induction ⋮ The hardness of resilience for nested aggregation query ⋮ Indefinite abductive explanations ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Prioritized logic programming and its application to commonsense reasoning ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases ⋮ Using possibilistic logic for modeling qualitative decision: answer set programming algorithms ⋮ Semantics for possibilistic answer set programs: uncertain rules versus rules with uncertain conclusions ⋮ Complexity results for explanations in the structural-model approach

Uses Software

• Datalog

Cites Work

• 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
• The expressive power of stratified logic programs
• Abduction versus closure in causal theories.
• Semantical considerations on nonmonotonic logic
• A logic for default reasoning
• Circumscription - a form of non-monotonic reasoning
• Non-monotonic logic. I
• General logical databases and programs: Default logic semantics and stratification
• The computational complexity of abduction
• Stable and extension class theory for logic programs and default logics
• On the greedy algorithm for satisfiability
• On the relations between stable and well-founded semantics of logic programs
• LOGIDATA+: deductive databases with complex objects
• The complexity of propositional closed world reasoning and circumscription
• An alternative approach to the semantics of disjunctive logic programs and deductive databases
• Generalized disjunctive well-founded semantics for logic programs.
• The expressive powers of the logic programming semantics
• Complexity and undecidability results for logic programming
• On the computational cost of disjunctive logic programming: Propositional case
• On the Relationship Between Abduction and Deduction
• Second order logic and the weak exponential hierarchies
• Classifying the computational complexity of problems
• SLDNFA: An abductive procedure for abductive logic programs
• A survey of complexity results for non-monotonic logics
• Autoepistemic logic
• The well-founded semantics for general logic programs
• Logic programming and knowledge representation
• The complexity of logic-based abduction
• Representing Incomplete Knowledge in Abductive Logic Programming
• An abductive framework for extended logic programming
• Abductive Logic Programming

This page was built for publication: Abduction from logic programs: Semantics and complexity