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
V. Chaudhri, W. Jarrold, and J. Pacheco. OWL: Experiences and Directions Workshop (OWLED), volume 216 of CEUR Workshop Proceedings, CEUR-WS.org, (2006)
G. Hillairet, F. Bertrand, J. Lafaye, and others. Proceedings of the 4th International Workshop on Semantic Web Enabled Software Engineering, SWESE, (2008)
A. Hildisch, J. Steurer, and R. Stolle. Proceedings of the 4th International Workshop on Software Engineering for Automotive Systems, page 4--. Washington, DC, USA, IEEE Computer Society, (2007)