A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Auch erschienen in: Foo, Norman u.a. (Hrsg.): PRICAI '96: topics in artificial intelligence. (Lecture notes in computer science ; 1114). Berlin u.a. : Springer, 1996. S. 121-131. ISBN 3-540-61532-6 <s> BIB001 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> From the Publisher: ::: This is the first textbook on formal concept analysis. It gives a systematic presentation of the mathematical foundations and their relation to applications in computer science, especially in data analysis and knowledge processing. Above all, it presents graphical methods for representing conceptual systems that have proved themselves in communicating knowledge. Theory and graphical representation are thus closely coupled together. The mathematical foundations are treated thoroughly and illuminated by means of numerous examples. <s> BIB002 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Given a finite set \(\mathcal{C} := \{ C_1, \ldots, C_n\}\) of description logic concepts, we are interested in computing the subsumption hierarchy of all least common subsumers of subsets of \(\mathcal{C}\). This hierarchy can be used to support the bottom-up construction and the structuring of description logic knowledge bases. The point is to compute this hierarchy without having to compute the least common subsumer for all subsets of \(\mathcal{C}\). We will show that methods from formal concept analysis developed for computing concept lattices can be employed for this purpose. <s> BIB003 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Description logics are embodied in several knowledge-based systems and are used to develop various real-life applications. Now in paperback, The Description Logic Handbook provides a thorough account of the subject, covering all aspects of research in this field, namely: theory, implementation, and applications. Its appeal will be broad, ranging from more theoretically oriented readers, to those with more practically oriented interests who need a sound and modern understanding of knowledge representation systems based on description logics. As well as general revision throughout the book, this new edition presents a new chapter on ontology languages for the semantic web, an area of great importance for the future development of the web. In sum, the book will serve as a unique resource for the subject, and can also be used for self-study or as a reference for knowledge representation and artificial intelligence courses. <s> BIB004 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Given a finite set C := {C 1 ,...,C n } of description logic concepts, we are interested in computing the subsumption hierarchy of all least common subsumers of subsets of C as well as the hierarchy of all conjunctions of subsets of C. These hierarchies can be used to support the bottom-up construction of description logic knowledge bases. The point is to compute the first hierarchy without having to compute the least common subsumer for all subsets of C, and the second hierarchy without having to check all possible pairs of such conjunctions explicitly for subsumption. We will show that methods from formal concept analysis developed for computing concept lattices can be employed for this purpose. <s> BIB005 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Designing ontologies and specifying axioms of the described domains is an expensive and error-prone task. Thus, we propose a method originating from Formal Concept Analysis which uses empirical data to systematically generate hypothetical axioms about the domain, which are represented to an ontology engineer for decision. In this paper, we focus on axioms that can be expressed as entailment statements in the description logic FLE . The proposed technique is an incremental one, therefore, in every new step we have to reuse the ax- iomatic information acquired so far. We present a sound and complete deduction calculus for FLE entailment statements. We give a detailed description of this multistep algorithm including a technique called empirical attribute reduction and demonstrate the pro- posed technique using an example from mathematics. We give a completeness result on the explored information and address the question of algorithm termination. Finally, we discuss possible appli- cations of our method. <s> BIB006 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Methods for computing the least common subsumer (lcs) are usually restricted to rather inexpressive Description Logics (DLs) whereas existing knowledge bases are written in very expressive DLs. In order to allow the user to re-use concepts defined in such terminologies and still support the definition of new concepts by computing the lcs, we extend the notion of the lcs of concept descriptions to the notion of the lcs w.r.t. a background terminology. We will both show a theoretical result on the existence of the least common subsumer in this setting, and describe a practical approach (based on a method from formal concept analysis) for computing good common subsumers, which may, however, not be the least ones. <s> BIB007 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> A logical view of formal concept analysis considers attributes of a formal context as unary predicates. In a first part, we propose an augmented definition that handles binary relations between objects. A Galois connection is defined on augmented contexts. It represents concept inheritance as usual, but also relations between concepts. As usual, labeling operators are also defined. In particular, concepts and relations are visible and labeled in a single structure. In a second part, we show how relations can be used for navigating in an augmented concept lattice. This part augments the theory of Logical Information Systems. An implementation is sketched, and first experimental results are presented. <s> BIB008 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> We propose an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the knowledge base and by a domain expert. The use of techniques from Formal Concept Analysis ensures that, on the one hand, the interaction with the expert is kept to a minimum, and, on the other hand, we can show that the extended knowledge base is complete in a certain, well-defined sense. <s> BIB009 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Proposing a certain notion of logical completeness as a novel quality criterion for ontologies, we identify and characterise a class of logical propositions which naturally extend domain and range restrictions commonly known from diverse ontology modelling approaches. We argue for the intuitivity of this kind of axioms and show that they fit equally well into formalisms based on rules as well as ones based on description logics. Extending the attribute exploration technique from formal concept analysis (FCA), we present an algorithm for the efficient interactive specification of all axioms of this form valid in a domain of interest.We compile some results that apply when role hierarchies and symmetric roles come into play and demonstrate the presented method in a small example. <s> BIB010 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> Formal Concept Analysis (FCA) can be used to analyze data given in the form of a formal context. In particular, FCA provides efficient algorithms for computing a minimal basis of the implications holding in the context. In this paper, we extend classical FCA by considering data that are represented by relational structures rather than formal contexts, and by replacing atomic attributes by complex formulae defined in some logic. After generalizing some of the FCA theory to this more general form of contexts, we instantiate the general framework with attributes defined in the Description Logic (DL) EL, and with relational structures over a signature of unary and binary predicates, i.e., models for EL. In this setting, an implication corresponds to a so-called general concept inclusion axiom (GCI) in EL. The main technical result of this paper is that, in EL, for any finite model there is a finite set of implications (GCIs) holding in this model from which all implications (GCIs) holding in the model follow. <s> BIB011 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> In a previous ICFCA paper we have shown that, in the De- scription Logics EL and ELgfp, the set of general concept inclusions hold- ing in a finite model always has a finite basis. In this paper, we address the problem of how to compute this basis efficiently, by adapting methods from formal concept analysis. <s> BIB012 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Introduction <s> In a previous paper, we have introduced an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the assertional part and by a domain expert. This approach, called knowledge base completion, was based on an extension of attribute exploration to the case of partial contexts. The present paper recalls this approach, and then addresses usability issues that came up during first experiments with a preliminary implementation of the completion algorithm. It turns out that these issues can be addressed by extending the exploration algorithm for partial contexts such that it can deal with implicational background knowledge. <s> BIB013
Formal Concept Analysis (FCA) BIB002 is a field of applied mathematics that aims to formalize the notions of a concept and a conceptual hierarchy by means of mathematical tools. On the other hand Description Logics (DLs) BIB004 are a class of logic-based knowledge representation formalisms that are used to represent the conceptual knowledge of an application domain in a structured way. Although the notion of a concept as a collection of objects sharing certain properties, and the notion of a conceptual hierarchy are fundamental to both FCA and DLs, the ways concepts are described and obtained differ significantly between these two research areas. In DLs, the relevant concepts of the application domain are formalized by so-called concept descriptions, which are expressions built from unary predicates (that are called atomic concepts), and binary predicates (that are called atomic roles) with the help of the concept constructors provided by the DL language. Then in a second step, these concept descriptions are used to describe properties of individuals occurring in the domain, and the roles are used to describe relations between these individuals. On the other hand, in FCA, one starts with a so-called formal context, which in its simplest form is a way of specifying which attributes are satisfied by which objects. A formal concept of such a context is a pair consisting of a set of objects called extent, and a set of attributes called intent such that the intent consists of exactly those attributes that the objects in the extent have in common, and the extent consists of exactly those objects that share all attributes in the intent. There are several differences between these approaches. First, in FCA one starts with a purely extensional description of the application domain, and then derives the formal concepts of this specific domain, which provide a useful structuring. In a way, in FCA the intensional knowledge is obtained from the extensional part of the knowledge. On the other hand, in DLs the intensional definition of a concept is given independently of a specific domain (interpretation), and the description of the individuals is only partial. Second, in FCA the properties are atomic, and the intensional description of a formal concept (by its intent) is just a conjunction of such properties. DLs usually provide a richer language for the intensional definition of concepts, which can be seen as an expressive, yet decidable sublanguage of first-order predicate logic. Despite these differences, there have been several attempts to bridge the gap between these two formalisms, and attempts to apply methods from one field to the other. For example, there have been efforts to enrich FCA with more complex properties similar to concept constructors in DLs    BIB008  . On the other hand, DL research has benefited from FCA methods to solve some problems encountered in knowledge representation using DLs  BIB001 BIB003 BIB005 BIB006 BIB007   BIB007 BIB009  BIB010 BIB011 BIB012 BIB013 . The present work aims to give an overview on these works done for bridging the gap between the two formalisms. In Section 2 we give a short introduction to DLs without going into technical details. We assume that the reader is familiar with FCA. We do not introduce FCA, we refer the reader to BIB002 for details. In Section 3 we summarize the existing work done by other researchers in the field. In Section 4 we summarize our own contributions to the field, and conclude with Section 5.