A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL

Franz BaaderFranz Baader

Download

Franz Baader
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL
In J. Hromkovic and M. Nagl, eds., Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004), volume 3353 of Lecture Notes in Computer Science, 177-188, 2004. Springer

Details
Bibtex

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.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaaderWG04,
  address = {Bad Honnef, Germany},
  author = {F. {Baader}},
  booktitle = {Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science {(WG 2004)}},
  editor = {J. {Hromkovic} and M. {Nagl}},
  pages = {177--188},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic $\mathcal{EL}$},
  volume = {3353},
  year = {2004},
}