On Finite Entailment of Non-Local Queries in Description Logics
This work addresses a theoretical computational complexity problem for knowledge representation and reasoning in AI, providing foundational results for non-local queries.
The paper tackled the problem of finite entailment for ontology-mediated queries with transitive closure in description logics ALCOI and ALCOQ, establishing 2EXPTIME upper bounds and a matching lower bound for ALC.
We study the problem of finite entailment of ontology-mediated queries. Going beyond local queries, we allow transitive closure over roles. We focus on ontologies formulated in the description logics ALCOI and ALCOQ, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of unions of conjunctive queries with transitive closure. We also provide a matching lower bound by showing that finite entailment of conjunctive queries with transitive closure in ALC is 2EXPTIME-hard.