Understanding the complexity of axiom pinpointing in lightweight description logics

作者：Penaloza Rafael^*; Sertkaya Baris

来源：Artificial Intelligence, 2017, 250: 80-104.

DOI：10.1016/j.artint.2017.06.002

• Description logics
• Axiom pinpointing
• Computational complexity
• Counting complexity
• Enumeration complexity

Lightweight description logics are knowledge representation formalisms characterised by the low complexity of their standard reasoning tasks. They have been successfully employed for constructing large ontologies that model domain knowledge in several different practical applications. In order to maintain these ontologies, it is often necessary to detect the axioms that cause a given consequence. This task is commonly known as axiom pinpointing.
In this paper, we provide a thorough analysis of the complexity of several decision, counting, and enumeration problems associated to axiom pinpointing in lightweight description logics.

• 出版日期2017-9