Description logic, theory combination, and all that. Essays dedicated to Franz Baader on the occasion of his 60th birthday
From MaRDI portal
Publication:2278575
Abstract: One of the main reasons to employ a description logic such as EL or EL++ is the fact that it has efficient, polynomial-time algorithmic properties such as deciding consistency and inferring subsumption. However, simply by adding negation of concepts to it, we obtain the expressivity of description logics whose decision procedure is {ExpTime}-complete. Similar complexity explosion occurs if we add probability assignments on concepts. To lower the resulting complexity, we instead concentrate on assigning probabilities to Axioms (GCIs). We show that the consistency detection problem for such a probabilistic description logic is NP-complete, and present a linear algebraic deterministic algorithm to solve it, using the column generation technique. We also examine and provide algorithms for the probabilistic extension problem, which consists of inferring the minimum and maximum probabilities for a new axiom, given a consistent probabilistic knowledge base.
Cited in
(7)- A posthumous contribution by Larry Wos: excerpts from an unpublished column
- Computing knowledge in equational extensions of subterm convergent theories
- Reasoning on with Defeasibility in ASP
- Involving cognitive science in model transformation for description logics
- Being polite is not enough (and other limits of theory combination)
- Linear-time temporal answer set programming
- Explaining reasoning results for description logic ontologies (invited paper)
This page was built for publication: Description logic, theory combination, and all that. Essays dedicated to Franz Baader on the occasion of his 60th birthday
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2278575)
