LATPub270: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Cyclic definitions in description logics have | |Abstract=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. | ||
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. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 50: | Zeile 38: | ||
year = {2003}, | year = {2003}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 13:24 Uhr
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
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
- 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},
}
