Terminological Cycles in a Description Logic with Existential Restrictions

Franz Baader
Terminological Cycles in a Description Logic with Existential Restrictions
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-02-02, 2002. LTCS-Report

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 report investigates subsumption in the presence of terminological cycles for the language EL, which allows for conjunction and existential restrictions. 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. These results are shown via a characterization of subsumption through the existence of certain simulation relations between nodes of the description graph associated with a given cyclic terminology.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Baader-LTCS-02-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-02-02},
  title = {Terminological Cycles in a Description Logic with Existential Restrictions},
  type = {LTCS-Report},
  year = {2002},
}

Terminological Cycles in a Description Logic with Existential Restrictions

Terminological Cycles in a Description Logic with Existential Restrictions

Franz BaaderFranz Baader