Non-standard inferences in description logics (Q5940719)

Description logics (DL) are a family of logic-based knowledge representation (KR) formalisms. They have their root in classical KR formalisms, in frames and semantic networks. The lack of a semantic specification of these formalisms lead to the development of the system KL-ONE equipped with a formal semantics. KL-ONE is considered the fist DL. The knowledge base of DL-systems consists of two parts -- TBox and ABox. A TBox stores the conceptual (terminological) knowledge of an application domain. In an ABox the assertional knowledge (a world description) is represented. Concept descriptions are the basic elements of DLs. They are built inductively from concept names (unary predicates), role names (binary predicates), and attribute names using the concept and role constructors. DLs are equipped with a formal logic-based semantics, which is usually defined in a model-theoretic way. The standard inference services of DLs include computing subconcept/superconcept relationships (subsumption) and checking whether an individual belongs to a concept (instance). Standard inferences are not sufficient when it comes to generating new concept descriptions from given ones, when concepts are specified using different vocabularies or if they are described on different levels of abstraction. The inferences involved are finding the least common subsumer (lcs), finding the most specific concept (msc) and matching of concept description (matching). At the time when the author's research started, the work concerning non-standard inference problems was at its very beginning. The main goal of the present book is to take non-standard inferences to the level that corresponds to the state of affairs in the investigation of standard inferences. The level can be characterized by the following tasks: to prove formal properties of non-standard inferences, and to provide correct algorithms for solving these inferences together with an analysis of their complexity. New results concerning the three non-standard inferences -- lcs, msc and matching -- are proven in the book. An in-depth analysis as well as provably sound and complete algorithms for lcs, msc and matching (for the description logics \({\mathcal A}{\mathcal L}{\mathcal N}{\mathcal S}\), \({\mathcal A}{\mathcal L}{\mathcal N}^*\), and \({\mathcal A}{\mathcal L}{\mathcal E}\) and for some of their sublanguages) are provided in the book.