- Titel
- Terminological cycles in a description logic with existential restrictions
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-790203
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 02-02
- Erstveröffentlichung
- 2002
- DOI
- https://doi.org/10.25368/2022.120
- Abstract (EN)
- Cyclic definitions in description logics have until now been investigated only for description logics allowing for value restrictions. Even for the most basic language FL₀, 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 FL₀, subsumption in EL remains polynomial, independent of wether 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.
- This is an updated version of the original report, in which some errors in Section 3.1 of the original report have been corrected.
- Freie Schlagwörter (DE)
- Subsumtion, Beschreibungslogik, zyklische Definition, Wertbeschränkung
- Freie Schlagwörter (EN)
- subsumption, description logic, cyclic definition, value restriction
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-790203
- Veröffentlichungsdatum Qucosa
- 30.05.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0