Publication Date


Document Type


Committee Members

Pascal Hitzler (Committee Chair), Andrew Hsu (Other), Thirunarayan Krishnaprasad (Committee Member), Michael Raymer (Committee Member), Mateen Rizki (Other)

Degree Name

Master of Science (MS)


This thesis is a formal study on how to extend the set of logic constructors of description logics languages, used for knowledge representation in the Semantic Web field to capture some of the previously exclusive rules expressivity. Description Logics, the logics underpinning the Web Ontology Language OWL, and rules are currently the most prominent paradigms used for modeling knowledge for the Semantic Web. While both of these approaches are based on classical logic, the paradigms also differ significantly, so that naive combinations result in undesirable properties such as undecidability. Recent work has shown that many rules can in fact be expressed in OWL. In this thesis we extend this work to include some types of rules previously excluded. We formally define a set of first order logic rules, C-Rules, which can be expressed within OWL extended with role conjunction. We also show that the use of nominal schemas results in even broader coverage. After formally defining C-Rules we tried to relax some of the restrictions imposed to roles in the expressive DL language sroiq. As it will be shown in Section ?? the description logic (DL) fragment ERI(u), which does not enforce role regularity restrictions, is the core of a larger DL fragment that results in a larger coverage of rules within the DL paradigm. Unfortunately, we show in this thesis that expanding ERI(u) with most of the classical DL constructors leads to undecidability. To support this statement, we formally present a set of reductions from the domino problem and the intersection of two free context grammars, both well known undecidable problems, for several minimal DL fragments. These results limit the possible integration of the description logics and rules paradigms and are of significant importance in order to find workable combinations of the two paradigms. Regretfully, most of this results are redundant preventing them for being publishable. Despite this fact we find these undecidability proofs interesting by themselves and include them as part of this thesis. We also present as part this thesis an addition to OWL 2 syntax to incorporate nominal schemas, which is a new description-logic style extension of OWL 2 which was recently proposed, and which makes is possible to express variable nominal classes within axioms in an OWL 2 ontology. Nominal schemas make it possible to express DL-safe rules of arbitrary arity within the extended OWL iii paradigm, hence covering the well-known DL-safe SWRL language. To express this feature, we extend OWL 2 syntax to include necessary and minimal modifications to both Functional and Manchester syntax grammars and mappings from these two syntaxes to Turtle/RDF. We also include several examples to clarify the proposal.

Page Count


Department or Program

Department of Computer Science

Year Degree Awarded