We study a Horn fragment called Horn-RegI of the regular description logic with inverse RegI , which extends the description logic ALC with inverse roles and regular role inclusion axioms characterized by finite automata. In contrast to the well-known Horn fragments EL, DL-Lite, DLP, Horn-SHIQ and Horn-SROIQ of description logics, Horn-RegI allows a form of the concept constructor “universal restriction” to appear at the left hand side of terminological inclusion axioms, while still has PTime data complexity. | VNU Journal of Science: Comp. Science & Com. Eng. Vol. 30, No. 4 (2014) 14–28 A Horn Fragment with PTime Data Complexity of Regular Description Logic with Inverse Linh Anh Nguyen1,2 , Thi-Bich-Loc Nguyen3 , Andrzej Szałas1,4 1 Institute of Informatics, University of Warsaw, Poland of Information Technology, VNU University of Engineering and Technology, Vietnam 3 Department of Information Technology, Hue University of Sciences, Vietnam 4 Department of Computer and Information Science, Link¨ oping University, Sweden 2 Faculty Abstract We study a Horn fragment called Horn-RegI of the regular description logic with inverse RegI , which extends the description logic ALC with inverse roles and regular role inclusion axioms characterized by finite automata. In contrast to the well-known Horn fragments EL, DL-Lite, DLP, Horn-SHIQ and Horn-SROIQ of description logics, Horn-RegI allows a form of the concept constructor “universal restriction” to appear at the left hand side of terminological inclusion axioms, while still has PTime data complexity. Namely, a universal restriction can be used in such places in conjunction with the corresponding existential restriction. We provide an algorithm with PTime data complexity for checking satisfiability of Horn-RegI knowledge bases. c 2014 Published by VNU Journal of Science. Manuscript communication: received 16 December 2013, revised 27 April 2014, accepted 13 May 2014 Corresponding author: Linh Anh Nguyen, nguyen@ Keywords: Description logics, Horn fragments, rule languages, Semantic Web. 1. Introduction Description logics (DLs) are variants of modal logics suitable for expressing terminological knowledge. They represent the domain of interest in terms of individuals (objects), concepts and roles. A concept stands for a set of individuals, a role stands for a binary relation between individuals. The DL SROIQ [1] founds the logical base of the Web Ontology Language OWL 2, which was recommended by W3C as a layer .
