A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL
Aus International Center for Computational Logic
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL
Franz BaaderFranz Baader
Franz Baader
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-04-02, 2004. LTCS-Report
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-04-02, 2004. LTCS-Report
- KurzfassungAbstract
In two previous papers we have investigates the problem of computing the least common subsumer (lcs) and the most specific concept (msc) for the description logic EL in the presence of terminological cycles that are interpreted with descriptive semantics, which is the usual first-order semantics for description logics. In this setting, neither the lcs nor the msc needs to exist. We were able to characterize the cases in which the lcs/msc exists, but it was not clear whether this characterization yields decidability of the existence problem. In the present paper, we develop a common graph-theoretic generalization of these characterizations, and show that the resulting property is indeed decidable, thus yielding decidability of the existence of the lcs and the msc. This is achieved by expressing the property in monadic second-order logic on infinite trees. We also show that, if it exists, then the lcs/msc 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-04-02,
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-04-02},
title = {A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL},
type = {LTCS-Report},
year = {2004},
}
