Terminological Cycles in a Description Logic with Existential Restrictions

Franz BaaderFranz Baader

Franz Baader
Terminological Cycles in a Description Logic with Existential Restrictions
In Georg Gottlob and Toby Walsh, eds., Proceedings of the 18th International Joint Conference on Artificial Intelligence, 325-330, 2003. Morgan Kaufmann

Details
Bibtex

KurzfassungAbstract
Cyclic definitions in description logics have until now been investigated only for description logics allowing for value restrictions. Even for the most basic language FL0, which allows for conjunction and value restrictions only, deciding subsumption in the presence of terminological cycles is a PSPACE-complete problem. This paper investigates subsumption in the presence of terminological cycles for the language EL, which allows for conjunction, existential restrictions, and the top-concept. In contrast to the results for FL0, subsumption in EL remains polynomial, independent of whether we use least fixpoint semantics, greatest fixpoint semantics, or descriptive semantics.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaderIJCAI03a,
  author = {Franz {Baader}},
  booktitle = {Proceedings of the 18th International Joint Conference on Artificial Intelligence},
  editor = {Georg {Gottlob} and Toby {Walsh}},
  pages = {325--330},
  publisher = {Morgan Kaufmann},
  title = {Terminological Cycles in a Description Logic with Existential Restrictions},
  year = {2003},
}