LATPub246: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 2: | Zeile 2: | ||
|ErsterAutorVorname=C. | |ErsterAutorVorname=C. | ||
|ErsterAutorNachname=Areces | |ErsterAutorNachname=Areces | ||
|FurtherAuthors= | |FurtherAuthors=Carsten Lutz | ||
}} | }} | ||
{{Inproceedings | {{Inproceedings | ||
| Zeile 10: | Zeile 10: | ||
|Month= | |Month= | ||
|Booktitle=Proceedings of the fourth Workshop on Hybrid Logics (HyLo'02) | |Booktitle=Proceedings of the fourth Workshop on Hybrid Logics (HyLo'02) | ||
|Editor=Carlos | |Editor=Carlos Areces and Patrick Blackburn and Maarten Marx and Ulrike Sattler | ||
|Note= | |Note= | ||
|Organization= | |Organization= | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract= | |Abstract=While the complexity of concept satisfiability in both ALCO, the basic description logic ALC enriched with nominals, and ALC(D), the extension of ALC with concrete domains, is known to be PSpace-complete, in this article we show that the combination ALCO(D) of these two logics can have a NExpTime-hard concept satisfiability problem (depending on the concrete domain D used). The proof is by a reduction of a NExpTime-complete variant of the domino problem to ALCO(D)-concept satisfiability. | ||
While the complexity of concept satisfiability in both ALCO, the basic description logic ALC enriched with nominals, and ALC(D), the extension of ALC with concrete domains, is known | |||
to be PSpace-complete, in this article we show that the combination ALCO(D) of these two logics can have a NExpTime-hard concept satisfiability problem (depending on the concrete | |||
domain D used). The proof is by a reduction of a NExpTime-complete variant of the domino problem to ALCO(D)-concept satisfiability. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 41: | Zeile 36: | ||
year = {2002}, | year = {2002}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Concrete Domains and Nominals United.
C. ArecesC. Areces, Carsten LutzCarsten Lutz
C. Areces, Carsten Lutz
Concrete Domains and Nominals United.
In Carlos Areces and Patrick Blackburn and Maarten Marx and Ulrike Sattler, eds., Proceedings of the fourth Workshop on Hybrid Logics (HyLo'02), 2002
Concrete Domains and Nominals United.
In Carlos Areces and Patrick Blackburn and Maarten Marx and Ulrike Sattler, eds., Proceedings of the fourth Workshop on Hybrid Logics (HyLo'02), 2002
- KurzfassungAbstract
While the complexity of concept satisfiability in both ALCO, the basic description logic ALC enriched with nominals, and ALC(D), the extension of ALC with concrete domains, is known to be PSpace-complete, in this article we show that the combination ALCO(D) of these two logics can have a NExpTime-hard concept satisfiability problem (depending on the concrete domain D used). The proof is by a reduction of a NExpTime-complete variant of the domino problem to ALCO(D)-concept satisfiability. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Areces-Lutz-HyLo-02,
author = {C. {Areces} and C. {Lutz}},
booktitle = {Proceedings of the fourth Workshop on Hybrid Logics (HyLo'02)},
editor = {Carlos {Areces} and Patrick {Blackburn} and Maarten {Marx} and Ulrike {Sattler}},
title = {Concrete Domains and Nominals United.},
year = {2002},
}
