Complexity of Abduction in the EL Family of Lightweight Description Logics

Meghyn BienvenuMeghyn Bienvenu

Download

Meghyn Bienvenu
Complexity of Abduction in the EL Family of Lightweight Description Logics
In Gerhard Brewka and Jérôme Lang, eds., Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR08), 220-230, 2008. AAAI Press

Details
Bibtex

KurzfassungAbstract
The complexity of logic-based abduction has been extensively studied for the case in which the background knowledge is represented by a propositional theory, but very little is known about abduction with respect to description logic knowledge bases. The purpose of the current paper is to examine the complexity of logic-based abduction for the EL family of lightweight description logics. We consider several minimality criteria for explanations (set inclusion, cardinality, prioritization, and weight) and three decision problems: deciding whether an explanation exists, deciding whether a given hypothesis appears in some acceptable explanation, and deciding whether a given hypothesis belongs to every acceptable explanation. We determine the complexity of these tasks for general TBoxes and also for EL and EL+ terminologies. We also provide results concerning the complexity of computing abductive explanations.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ bienvenu-kr08,
  author = {Meghyn {Bienvenu}},
  booktitle = {Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR08)},
  editor = {Gerhard {Brewka} and J{\'e}r{\^o}me {Lang}},
  pages = {220--230},
  publisher = {AAAI Press},
  title = {Complexity of Abduction in the EL Family of Lightweight Description Logics},
  year = {2008},
}