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 |
||
| 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= | ||
Version vom 20. März 2015, 16:28 Uhr
Concrete Domains and Nominals United.
C. ArecesC. Areces, C. LutzC. Lutz
C. Areces, C. 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 knownto 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},
}
