Motik, Boris
Reasoning in Description Logics using Resolution and Deductive Databases
Universität Karlsruhe, Fak. f. Wirtschaftswissenschaften. Diss. v. 09.01.2006.
We extend the description logic EL++ with reflexive roles
and range restrictions, and show that subsumption remains tractable if
a certain syntactic restriction is adopted. We also show that subsumption
becomes PSpace-hard (resp. undecidable) if this restriction is weakened
(resp. dropped). Additionally, we prove that tractability is lost when
symmetric roles are added: in this case, subsumption becomes ExpTime-
hard
C. d'Amato, N. Fanizzi, and F. Esposito. Proceedings of the 2006 ACM Symposium on Applied Computing (SAC 2006), April 23-27, 2006, Dijon, France, page 1695--1699. ACM, New York, NY, USA, (2006)
N. Fanizzi, and C. d'Amato. Foundations of Intelligent Systems, 16th International Symposium,, volume 4203 of Lecture Notes in Computer Science, page 322-331. Springer, Berlin--Heidelberg, Germany, (2006)