DESCRIPTION LOGICS

Eliminating second-order quantification for description logics



Eliminating second-order quantification for description logics

Abstract

Information can often be expressed more succinctly using second-order quantification. However, reasoning remains incomplete for the second-order logic and thus it cannot be fully automated. For this reason, most of the times, the formulae of second-order logic are equivalently expressed as the first-order logic formulae. Second-order quantifier elimination techniques are useful for languages with limited expression, such as description logics.

This project focuses on the description logics for equivalent reduction of elimination, of the second-order quantifier. Thus, the goals of the project include equivalently reducing description logic expressions that involve second-order quantification over concept symbols to first-order formulae. The solutions for the same problem already exist for modal logics.

The major aims of the project include (i) to transfer a solution of description logics, exploiting the well-known close relationships between description logics and modal logics, and (ii) to invent a tool for eliminating second-order quantification for description logic expressions, and to implement it.

Introduction

The purpose of applying logics in computer science deals with developing the languages. These languages are used to model the situations that are commonly encountered by the computer science professionals. Research shows that a formal approach can be achieved to justify reason about such situations. Reasoning about situations refers to the process of constructing arguments about them. This reasoning allows expressing sentences in a logical structure and aims to make the arguments valid. Also, using these justifications, the arguments can be defended more rigorously, or can be executed on a machine conveniently.

Description logics are a type of logic which refers to a family of formalisms. This family concentrates around the concepts, roles and individuals. These logics are considered as the syntactic variants of decidable fragments, derived from the conventional first-order logic. Description logics are one of the knowledge representation formalisms. These logics serve a variety of paradigms, such as frame-based systems and KL-One.

The description logics fundamentally play a vital role, to specify the concepts and relevant hierarchies. The description logics also deal with the properties that reduce to subsumption. Knowledge representation systems are often assumed to be equipped with advanced reasoning machinery, usually employing non-monotonic or common-sense forms of reasoning. There have been attempts to integrate description logics with such forms of reasoning; however they do not directly employ second-order formalisms. On the other hand, common-sense and non-monotonic reasoning can, in many cases, be directly formalized within classical second-order logic. Therefore, we follow the ways to integrate description logics with common-sense reasoning that depends on extending description logics by second-order quantifiers allowing one to quantify over concepts.

The rest of the report is organized as follows. In section 2.1, the report introduces two fundamental logics(propositional logics and predicate logics. This section helps the reader in developing the necessary concepts of conventional logic apparatus and notations. In section 2.2 and 2.3, the report presents in depth knowledge about the description and modal logics, respectively. This section also includes the syntax and semantics of the prototypical DL ALC and ...