A Parameterized Complexity View on Description Logic Reasoning
Description logics are knowledge representation languages that have been designed to strike a balance between expressivity and computational tractability. Many different description logics have been developed, and numerous computational problems for these logics have been studied for their computational complexity. However, essentially all complexity analyses of reasoning problems for description logics use the one-dimensional framework of classical complexity theory. The multi-dimensional framework of parameterized complexity theory is able to provide a much more detailed image of the complexity of reasoning problems. In this paper we argue that the framework of parameterized complexity has a lot to offer for the complexity analysis of description logic reasoning problems---when one takes a progressive and forward-looking view on parameterized complexity tools. We substantiate our argument by means of three case studies. The first case study is about the problem of concept satisfiability for the logic ALC with respect to nearly acyclic TBoxes. The second case study concerns concept satisfiability for ALC concepts parameterized by the number of occurrences of union operators and the number of occurrences of full existential quantification. The third case study offers a critical look at data complexity results from a parameterized complexity point of view. These three case studies are representative for the wide range of uses for parameterized complexity methods for description logic problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Complexity of Limited Belief Reasoning -- The Quantifier-Free Case
The classical view of epistemic logic is that an agent knows all the logical consequences of their knowledge base. This assumption of logical omniscience is often unrealistic and makes reasoning computationally intractab…
Ontology-Mediated Querying on Databases of Bounded Cliquewidth
We study the evaluation of ontology-mediated queries (OMQs) on databases of bounded cliquewidth from the viewpoint of parameterized complexity theory. As the ontology language, we consider the description logics $\mathca…
On the Non-Monotonic Description Logic $\mathcal{ALC}$+T$_{\mathsf{min}}$
In the last 20 years many proposals have been made to incorporate non-monotonic reasoning into description logics, ranging from approaches based on default logic and circumscription to those based on preferential semanti…
BlockingTowards Statistical Reasoning in Description Logics over Finite Domains (Full Version)
We present a probabilistic extension of the description logic $\mathcal{ALC}$ for reasoning about statistical knowledge. We consider conditional statements over proportions of the domain and are interested in the probabi…
Defeasible reasoning in Description Logics: an overview on DL^N
DL^N is a recent approach that extends description logics with defeasible reasoning capabilities. In this paper we provide an overview on DL^N, illustrating the underlying knowledge engineering requirements as well as th…