Concrete Domains and Nominals United.

C. ArecesC. Areces, C. LutzC. Lutz

Datei:ArecesLutz02.ps.gz

Download

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

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