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. Ma, V. Smith, M. Jaggi, M. Jordan, P. Richtárik, и M. Takáč. (2015)cite arxiv:1502.03508Comment: ICML 2015: JMLR W&CP volume37, Proceedings of The 32nd International Conference on Machine Learning, pp. 1973-1982.
D. Kingma, и J. Ba. (2014)cite arxiv:1412.6980Comment: Published as a conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
D. Povey, X. Zhang, и S. Khudanpur. (2014)cite arxiv:1410.7455Comment: Accepted as workshop contribution to ICLR 2015. 12 pages plus 16 pages of appendices, International Conference on Learning Representations (ICLR): Workshop track, 2015. 2 sets of minor fixes post-publication..