资源分类
》 资源 》论文》Query Answering in Description Logics with Transitive Roles

Query Answering in Description Logics with Transitive Roles

2019-11-15 | |  75 |   43 |   0

Abstract We study the computational complexity of conjunctive query answering w.r.t. ontologies formulated in fragments of the description logic SHIQ. Our main result is the identifification of two new sources of complexity: the combination of transitive roles and role hierarchies which results in 2-EXPTIMEhardness, and transitive roles alone which result in CO-NEXPTIME-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2-EXPTIME-hard. We also show that conjunctive query answering with transitive roles, but without inverse roles and role hierarchies, remains in EXPTIME if the ABox is tree-shaped

上一篇：Decomposition of Declarative Knowledge Bases with External Functions

下一篇：Bidirectional Answer Set Programs with Function Symbols

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...