it gb
it gb

G. Pozzato - V. Gliozzi - Estensioni Nonmonotone di Logiche Descrittive

The family of Description Logics (DLs) is one of the most important classes of formalisms for knowledge representation. They have a well-defined semantics based on first-order logic and offer a good trade-off between expressivity and complexity. DLs have been successfully implemented by a range of systems and they are at the basis of languages for the semantic web such as OWL.

A DL knowledge base (KB) contains two components: the TBox, containing the definition of concepts (and possibly roles) and a specification of inclusion relations among them, and the ABox containing instances of concepts and roles. Since the very objective of the TBox is to build a taxonomy of concepts, the need of representing prototypical properties and of reasoning about defeasible inheritance of such properties naturally arises.

Nonmonotonic extensions of Description Logics have been actively investigated since the early 90s, [1, 4]. In spite of the number of works in this direction, finding a solution to the problem of extending DLs for reasoning about prototypical properties seems far from being solved. The most well known semantics for nonmonotonic reasoning have been used to the purpose, from default logic [1], to circumscription [2], to MKNF [4, 9], to preferential reasoning [6], to rational closure [3].

In the last years [5, 6] we have introduced a simple but powerful nonmonotonic extension of DLs based on a “typicality” operator: in this approach “typical” or “normal” properties can be directly specified by means of an operator T enriching the underlying DL. In this logic one can express defeasible inclusions such as “typical students are social networks users” with T(Student) ⊑ SocialNetworkUser.

As a difference with standard DLs, one can consistently express exceptions and reason about defeasible inheritance as well. For instance, a knowledge base can consistently express that “normally, a student does not pay taxes”, whereas “a typical working student pays taxes” as follows:

T(Student) ⊑ ¬TaxPayer T(Student ⊓ Worker) ⊑ TaxPayer

In this extension, standard models are extended by a function f which selects the typical/most normal instances of any concept C, i.e. the extension of T(C) is defined as (T(C))I = f (CI). The function f satisfies a set of postulates that are a restatement of Kraus, Lehmann and Magidor’s axioms of rational logic R. This allows the typicality operator to inherit well-established properties of nonmonotonic reasoning, such as specificity.

The resulting logic is however too weak in several application domains. Indeed, although the operator T is nonmonotonic (T(C) ⊑ E does not imply T(C ⊓ D) ⊑ E), the logic itself is monotonic, in the sense that if the fact F follows from a given knowledge base KB, then F also follows from any KB’ ⊇ KB. As a consequence, unless a KB contains explicit assumptions about typicality of individuals, there is no way of inferring defeasible properties about them. In order to overcome this limit and perform useful inferences, we have introduced a nonmonotonic extension of the logic of typicality based on a minimal model semantics [7], corresponding to a notion of rational closure as defined in [8] for propositional logic. Intuitively, the idea is to restrict our consideration to (canonical) models that maximize typical instances of a concept when consistent with the knowledge base. From a semantic point of view, the nonmonotonic logic is based on a preference relation among models and a notion of minimal entailment restricted to models that are minimal with respect to such preference relation. We have also shown that, as a difference with other proposals of nonmonotonic DLs, reasoning in the logic of typicality is essentially inexpensive, in the sense that the complexity of minimal entailment in the considered DLs is ExpTime-complete as for the underlying standard DL.


References

[1] F. Baader and B. Hollunder. Priorities on defaults with prerequisites, and their application in treating specificity in terminological

default logic. Journal of Automated Reasoning (JAR), 15(1):41–68, 1995.

[2] P. A. Bonatti, C. Lutz, and F. Wolter. DLs with Circumscription. In KR, pages 400–410, 2006.

[3] G. Casini and U. Straccia. Defeasible Inheritance-Based Description Logics. J. of Artificial Intelligence Research, 48:415–473, 2013.

[4] F. M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation as failure. ACM Transactions on

Computational Logics (ToCL), 3(2):177–225, 2002.

[5] L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. ALC+T: a preferential extension of description logics. Fundamenta Informat-

icae, 96:341–372, 2009.

[6] L. Giordano, V. Gliozzi, N. Olivetti, and G.L. Pozzato. A NonMonotonic Description Logic for Reasoning About Typicality. Artificial

Intelligence, 195:165 – 202, 2013.

[7] L. Giordano, V. Gliozzi, N. Olivetti, and G.L. Pozzato. Semantic characterization of rational closure: From propositional logic to

description logics. Artificial Intelligence, 226:1–33, 2015.

[8] D. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial Intelligence, 55(1):1–60, 1992. [9] B. Motik and R. Rosati. Reconciling Description Logics and rules. Journal of the ACM, 57(5), 2010.