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
r. Kurt Bollacker is a computer scientist with a research background in the areas of machine learning, digital libraries, semantic networks, and electro-cardiographic modeling. He received a Ph.D. in Computer Engineering from The University Of Texas At Austin, was co-creator of the Citeseer research tool as a visiting researcher at the NEC Research Institute, was the technical director of the Internet Archive, and a biomedical research engineer at the Duke University Medical Center. He is currently pursuing research into long term digital archiving as the Digital Research Director at the Long Now Foundation, and is a scientist at Metaweb Technologies.
F. Baader, B. Ganter, B. Sertkaya, and U. Sattler. Proceedings of the 20th international joint conference on Artifical intelligence, page 230--235. San Francisco, CA, USA, Morgan Kaufmann Publishers Inc., (2007)
B. Motik. Proceedings of the 18th International Conference on Conceptual Structures (ICCS 2010), volume 6208 of Lecture Notes in Computer Science, page 10-12. Springer, (2010)
F. Baader, B. Ganter, B.Sertkaya, and U. Sattler. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07), page 230--235. (2007)
D. Calvanese, G. Giacomo, and M. Lenzerini. Computational Logic: Logic Programming and Beyond, volume 2408 of Lecture Notes in Computer Science, page 41--60. Springer Berlin / Heidelberg, (2002)
S. Grimm, B. Motik, and C. Preist. Proc. of the 3rd European Semantic Web Conference (ESWC 2006), volume 4011 of LNCS, page 575--589. Budva, Montenegro, Springer, (June 2006)
V. Haarslev, and R. Möller. Automated Reasoning: First International Joint
Conference (IJCAR) 2001, volume 2083 of Lecture Notes in Computer Science, page 701. Siena, Italy, Springer-Verlag, (June 2001)
S. Dasiopoulou, I. Kompatsiaris, and M. Strintzis. Semantic Multimedia, Third International Conference on Semantic and Digital Media Technologies, SAMT 2008, Koblenz, Germany, page 31-46. (2008)
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)
N. Fanizzi, and C. d'Amato. Proceedings of the 11th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES 2007), XVII Italian Workshop on Neural Networks,, 4692, page 148--155. Springer, Berlin--Heidelberg, Germany, (2007)
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)
W. Cohen, and H. Hirsh. Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KR'94), May 24-27, 1994, Bonn, Germany, page 121--133. Morgan-Kauffman Publishers, San Francisco, CA, USA, (1994)
A. Borgida, T. Walsh, and H. Hirsh. Proceedings of the 2005 International Workshop on Description Logics (DL2005), July 26-28, 2005, Edinburgh, Scotland, UK, volume 147 of CEUR Workshop Proceedings, CEUR-WS.org, (2005)
A. Kalyanpur, B. Parsia, M. Horridge, and E. Sirin. Proceedings of the 6th International Semantic Web Conference and 2nd Asian Semantic Web Conference (ISWC/ASWC2007), Busan, South Korea, volume 4825 of LNCS, page 267--280. Berlin, Heidelberg, Springer Verlag, (November 2007)
S. Konstantopoulos, and G. Apostolikas. Proceedings of International IFIP Workshop of Semantic Web and Web Semantics (IFIP-SWWS 07), Algarve, 29--30 Nov. 2007, (2007)
F. Baader. Proceedings of the International Symposium on Knowledge Retrieval, Use, and Storage for Efficiency, KRUSE 95, page 168--178. Santa Cruz, USA, (1995)
J. Metzger, F. Ber, and A. Napoli. Proceedings of the 11th International Conference on Conceptual Structures (ICCS 2003), volume 2746 of Lecture Notes in Computer Science, page 215-228. Springer, (2003)
F. Baader. Proceedings of the 11th International Conference on Conceptual Structures (ICCS 2003), volume 2746 of Lecture Notes in Computer Science, page 117-130. Springer, (2003)
I. Horrocks. Proceedings of the 13th International Conference on Conceptual Structures (ICCS 2005), volume 3596 of Lecture Notes in Computer Science, page 78-90. Springer, (2005)