Most modern formalisms used in Databases and Arti cial Intelligence for describing an application domain are based on the notions of class (or concept) and relationship among classes. One interesting feature of such formalisms is the possibility of de ning a class, i.e., providing a set of properties that precisely characterize the instances of the class. Many recent articles point out that there are several ways of assigning a meaning to a class de nition containing some sort of recursion. In this paper, we argue that, instead of choosing a single style of semantics, we achieve better results by adopting a formalism that allows for di erent semantics to coexist. We demonstrate the feasibility of our argument, by presenting a knowledge representation formalism, the description logic ALCQ, with the above characteristics. In addition to the constructs for conjunction, disjunction, negation, quanti ers, and quali ed number restrictions, ALCQ includes special xpoint constructs to express (suitably interpreted) recursive de nitions. These constructs enable the usual frame-based descriptions to be combined with de nitions of recursive data structures such as directed acyclic graphs, lists, streams, etc. We establish several properties of ALCQ, including the decidability and the computational complexity of reasoning, by formulating a correspondence with a particular modal logic of programs called the modal mu-calculus.
Download Full PDF Version (Non-Commercial Use)