The Instance Problem and the Most Specific Concept in the Description Logic EL w.r.t. Terminological Cycles with Descriptive Semantics
From International Center for Computational Logic
The Instance Problem and the Most Specific Concept in the Description Logic EL w.r.t. Terminological Cycles with Descriptive Semantics
Franz BaaderFranz Baader
Franz Baader
The Instance Problem and the Most Specific Concept in the Description Logic EL w.r.t. Terminological Cycles with Descriptive Semantics
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-03-01, 2003. LTCS-Report
The Instance Problem and the Most Specific Concept in the Description Logic EL w.r.t. Terminological Cycles with Descriptive Semantics
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-03-01, 2003. LTCS-Report
- KurzfassungAbstract
and non-standard inferences in the presence of terminological cycles for the description logic EL, which allows for conjunctions, existential restrictions, and the top concept. Regarding standard inference problems, it was shown there that the subsumption problem remains polynomial for all three types of semantics usually considered for cyclic definitions in description logics, and that the instance problem remains polynomial for greatest fixpoint semantics. Regarding non-standard inference problems, it was shown that, w.r.t. greatest fixpoint semantics, the least common subsumer and the most specific concept always exist and can be computed in polynomial time, and that, w.r.t. descriptive semantics, the least common subsumer need not exist. The present report is concerned with two problems left open by this previous work, namely the instance problem and the problem of computing most specific concepts w.r.t. descriptive semantics, which is the usual first-order semantics for description logics. We will show that the instance problem is polynomial also in this context. Similar to the case of the least common subsumer, the most specific concept w.r.t. descriptive semantics need not exist, but we are able to characterize the cases in which it exists and give a decidable sufficient condition for the existence of the most specific concept. Under this condition, it can be computed in polynomial time. - Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ Baader-LTCS-03-01,
address = {Germany},
author = {F. {Baader}},
institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
number = {LTCS-03-01},
title = {The Instance Problem and the Most Specific Concept in the Description Logic {$\mathcal{EL}$} w.r.t.\ Terminological Cycles with Descriptive Semantics},
type = {LTCS-Report},
year = {2003},
}
