LATPub146: 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 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname= | |ErsterAutorVorname= | ||
|ErsterAutorNachname=S | |ErsterAutorNachname=S .Tobies | ||
|FurtherAuthors= | |FurtherAuthors= | ||
}} | }} | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=We examine the complexity and expressivity of the combination of the | |Abstract=We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into C^2, the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as C^2 but does not reach its expressive power. | ||
Description Logic ALCQI with a terminological formalism based on cardinality | |||
restrictions on concepts. This combination can naturally be embedded into | |||
C^2, the two variable fragment of predicate logic with counting quantifiers. | |||
We prove that ALCQI has the same complexity as C^2 but does not reach its | |||
expressive power. | |||
| Zeile 49: | Zeile 42: | ||
year = {1999}, | year = {1999}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 13:24 Uhr
A NExpTime-complete Description Logic Strictly Contained in C^2
S .TobiesS .Tobies
S .Tobies
A NExpTime-complete Description Logic Strictly Contained in C^2
In J. Flum and M. Rodríguez-Artalejo, eds., Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL-99), LNCS 1683, 292-306, 1999. Springer
A NExpTime-complete Description Logic Strictly Contained in C^2
In J. Flum and M. Rodríguez-Artalejo, eds., Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL-99), LNCS 1683, 292-306, 1999. Springer
- KurzfassungAbstract
We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into C^2, the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as C^2 but does not reach its expressive power.
There is also an extended technical report.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Tobies-CSL-99,
author = {{S~.Tobies}},
booktitle = {Proceedings of the Annual Conference of the European Association for Computer Science Logic {(CSL-99)}},
editor = {J. {Flum} and M. {Rodr{\'i}guez-Artalejo}},
pages = {292--306},
publisher = {Springer-Verlag},
series = {LNCS 1683},
title = {A {NExpTime}-complete Description Logic Strictly Contained in {$C^2$}},
year = {1999},
}
