Concrete Domains and Nominals United.

C. ArecesC. Areces, Carsten LutzCarsten Lutz

Datei:ArecesLutz02.ps.gz

Download

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

Details
Bibtex

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},
}