ALC + T: a Preferential Extension of Description Logics

Issue title: Advances in Computational Logic (CIL C08)

Article type: Research Article

Authors: Giordano, Laura | Olivetti, Nicola | Gliozzic, Valentina | Pozzato, Gian Luca

Affiliations: Dipartimento di Informatica Università del Piemonte Orientale "A. Avogadro" viale Teresa Michel, 11 - 15121, Alessandria, Italy. E-mail: [email protected] | LSIS-UMR CNRS 6168 Université "Paul Cézanne" Aix en Provence, France. E-mail: [email protected] | Dipartimento di Informatica Università degli Studi di Torino c.so Svizzera 185, 10145 Torino, Italy. E-mail: {gliozzi,pozzato}@di.unito.it

Abstract: We extend the Description Logic ALC with a "typicality" operator T that allows us to reason about the prototypical properties and inheritance with exceptions. The resulting logic is called ALC + T. The typicality operator is intended to select the "most normal" or "most typical" instances of a concept. In our framework, knowledge bases may then contain, in addition to ordinary ABoxes and TBoxes, subsumption relations of the form "T(C) is subsumed by P", expressing that typical C-members have the property P. The semantics of a typicality operator is defined by a set of postulates that are strongly related to Kraus-Lehmann-Magidor axioms of preferential logic P. We first show that T enjoys a simple semantics provided by ordinary structures equipped with a preference relation. This allows us to obtain a modal interpretation of the typicality operator. We show that the satisfiability of anALC+Tknowledge base is decidable and it is precisely EXPTIME. We then present a tableau calculus for deciding satisfiability of ALC + T knowledge bases. Our calculus gives a (suboptimal) nondeterministic-exponential time decision procedure for ALC + T. We finally discuss how to extend ALC + T in order to infer defeasible properties of (explicit or implicit) individuals. We propose two alternatives: (i) a nonmonotonic completion of a knowledge base; (ii) a "minimal model" semantics for ALC + T whose intuition is that minimal models are those that maximise typical instances of concepts.

Keywords: Description Logics, Prototypical Reasoning, Tableaux Calculi

DOI: 10.3233/FI-2009-182

Journal: Fundamenta Informaticae, vol. 96, no. 3, pp. 341-372, 2009