Horn Knowledge Bases in Regular Description Logics with PTIME Data Complexity

Article type: Research Article

Authors: Nguyen, Linh Anh

Affiliations: Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland. [email protected]

Note: [] Address for correspondence: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland Supported in part by the Polish MNiSW grant N N206 3982 33.

Abstract: Developing a good formalism and an efficient decision procedure for the instance checking problem is desirable for practical application of description logics. The data complexity of the instance checking problem is coNP-complete even for Horn knowledge bases in the basic description logic ALC. In this paper, we present and study weakenings with PTIME data complexity of the instance checking problem for Horn knowledge bases in regular description logics. We also study cases when the weakenings are an exact approximation. In contrast to previous related work of other authors, our approach deals with the case when the constructor ∀ is allowed in premises of program clauses that are used as terminological axioms.

Keywords: Horn knowledge bases, description logics, regular grammar logics

DOI: 10.3233/FI-2010-353

Journal: Fundamenta Informaticae, vol. 104, no. 4, pp. 349-384, 2010