Query Answering in the Description Logic S
Meghyn Bienvenu, Thomas Eiter, Carsten Lutz, Magdalena Ortiz, Mantas Šimkus · 2010
Abstract. We consider the complexity of answering conjunctive queries in the description logic S, i.e., in ALC extended with transitive roles. While a co-NEXPTIME lower bound was recently established in [4], the best known upper bound was 2-EXPTIME. In this paper, we concentrate on the case where only a single transitive role (and no other role) is present and establish a tight co-NEXPTIME upper bound. 1