Concrete Domains and Nominals United

C. Areces and C. Lutz. Concrete Domains and Nominals United. In Proceedings of HyLo@LICS, Copenhagen, Denmark, 2002.

Download

[pdf] 

Abstract

While the complexity of concept satisfiability in both ALCO, the basic descrip- tion 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.

BibTeX

@InProceedings{Areces2002e,
  author =       "C. Areces and C. Lutz",
  booktitle =    "Proceedings of {HyLo@LICS}",
  title =        "Concrete Domains and Nominals United",
  year =         "2002",
  abstract =     "While the complexity of concept satisfiability in both
                 ALCO, the basic descrip- tion 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.",
  address =      "Copenhagen, Denmark",
  editor =       "C. Areces and P. Blackburn and M. Marx and U.
                 Sattler",
}