A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Applying FCA methods in DLs <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> Applying FCA methods in DLs <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> BIB002 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Applying FCA methods in DLs <s> A pattern reading device comprises feed mechanism for storing a sheaf of cards carrying patterns and feeding said cards one by one, a conveying mechanism having a plurality of pinch members at regular intervals to pinch the forward edge of each fed card and convey said card to a reading section, and an optical reader provided in said reading section for reading patterns on said cards. <s> BIB003 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Applying FCA methods in DLs <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> BIB004 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Applying FCA methods in DLs <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> BIB005
Subsumption hierarchy of conjunctions of DL concepts In  , Baader has used FCA for an efficient computation of an extended subsumption hierarchy of a set of DL concepts. More precisely, he used attribute exploration for computing the subsumption hierarchy of all conjunctions of a set of DL concepts. The main motivation for this work was to determine the interaction between defined concepts, which might not easily be seen by just looking at the subsumption hierarchy of defined concepts. In order to explain this, the following example has been given: assume that the defined concept NoDaughter stands for those people who have no daughters, NoSon stands for those people who have no sons, and NoSmallChild stands for those people who have no small children. Obviously, there is no subsumption relationship between these three concepts. On the other hand, the conjunction NoDaughter ⊓ NoSon is subsumed by NoSmallChild, i.e., if an individual a belongs to NoSon and NoDaughter, it also belongs to NoSmallChild. However, this cannot be derived from the information that a belongs to NoSon and NoDaughter by just looking at the subsumption hierarchy. This small example demonstrates that runtime inferences concerning individuals can be made faster by precomputing the subsumption hierarchy not only for defined concepts, but also for all conjunctions of defined concepts. To this purpose, Baader defined a formal context whose attributes were the defined DL concepts, and whose objects were all possible counterexamples to subsumption relationships, i.e., interpretations together with an element of the interpretation domain. This formal context has the property that its concept lattice is isomorphic to the required subsumption hierarchy, namely the subsumption hierarchy of conjunctions of the defined DL concepts. However, this formal context has the disadvantage that a standard subsumption algorithm can not be used as expert for this context within attribute exploration. In order to overcome this problem, the approach was reconsidered in BIB004 and a new formal context that has the same properties but for which a usual subsumption algorithm could be used as expert was introduced. Subsumption hierarchy of conjunctions and disjunctions of DL concepts In BIB001 , Stumme has extended the abovementioned subsumption hierarchy further with disjunctions of DL concepts. More precisely, he presented how the complete lattice of all possible combinations of conjunctions and disjunctions of the concepts in a DL TBox can be computed by using FCA. To this aim, he used another knowledge acquisition tool of FCA instead of attribute exploration, namely distributive concept exploration  . In the lattice computed by this method, the supremum of two DL concepts in the lattice corresponds to the disjunction of these concepts. Subsumption hierarchy of least common subsumers In BIB002 Baader and Molitor have used FCA for supporting bottom-up construction of DL knowledge bases. In the bottom-up approach, the knowledge engineer does not directly define the concepts of her application domain, but she gives typical examples of a concept, and the system comes up with a concept description for these examples. The process of computing such a concept description consists of first computing the most specific concepts that the given examples belong to, and then computing the least common subsumer of these concepts. Here the choice of examples is crucial for the quality of the resulting concept description. If the examples are too similar, the resulting concept description will be too specific; conversely, if they are too distinct, the resulting concept description will be too general. In order to overcome this, Baader and Molitor have used attribute exploration for computing the subsumption hierarchy of all least common subsumers of a given set of concepts. In this hierarchy one can easily see the position of the least concept description that the chosen examples belong to, and decide whether these examples are appropriate for obtaining the intended concept description. However, there may be exponentially many least common subsumers, and depending on the DL in use, both the least common subsumer computation and subsumption test can be expensive operations. The use of attribute exploration provides us with complete information on how this hierarchy looks like without explicitly computing all least common subsumers and classifying them. Relational exploration In his Ph.D thesis  , Rudolph has combined DLs and FCA for acquiring complete relational knowledge about an application domain. In his approach, which he calls relational exploration, he uses DLs for defining FCA attributes, and FCA for refining DL knowledge bases. More precisely, DLs makes use of the interactive knowledge acquisition method of FCA, and FCA benefits from DLs in terms of expressing relational knowledge. In BIB005  , Rudolph uses the DL F LE for this purpose, which is the DL that allows for the constructors conjunction, existential restriction, and value restriction. In his previous work BIB003 , he uses the DL EL, which allows for the constructors conjunction and existential restriction. In both cases, he defines the semantics by means of a special pair of formal contexts called binary power context family, which are used for expressing relations in FCA. Binary power context families have also been used for giving semantics to conceptual graphs. In order to collect information about the formulae expressible in F LE, in BIB005  he defines a formal context called F LE-context. The attributes of this formal context are F LE-concept descriptions, and the objects are the elements of the domain over which these concept descriptions are interpreted. In this context, an object g is in relation with an attribute m if and only if g is in the interpretation of m. Thus, an implication holds in this formal context if and only if in the given model the concept description resulting from the conjunction of the attributes in the premise of the implication is subsumed by the concept description formed from the conclusion. This is how implications in F LE-contexts give rise to subsumption relationships between F LE concept descriptions. In order to obtain complete knowledge about the subsumption relationships in the given model between arbitrary F LE concepts, Rudolph gives a multi-step exploration algorithm. In the first step of the algorithm, he starts with an F LEcontext whose attributes are the atomic concepts occurring in a knowledge base. In exploration step i + 1, he defines the set of attributes as the union of the set of attributes from the first step and the set of concept descriptions formed by universally quantifying all attributes of the context at step i w.r.t. all atomic roles, and the set of concept descriptions formed by existentially quantifying all concept intents of the context at step i w.r.t all atomic roles. Rudolph points out that, at an exploration step, there can be some concept descriptions in the attribute set that are equivalent, i.e., attributes that can be reduced. To this aim, he introduces a method that he calls empiric attribute reduction. In principle, it is possible to carry out infinitely many exploration steps, which means that the algorithm will not terminate. In order to guarantee termination, Rudolph restricts the number of exploration steps. After carrying out i steps of exploration, it is then possible to decide subsumption (w.r.t. the given model) between any F LE concept descriptions up to role depth i just by using the implication bases obtained as a result of the exploration steps. In addition, he also characterizes the cases where finitely many steps are sufficient to acquire complete information for deciding subsumption between F LE concept descriptions with arbitrary role depth. Rudolph argues that his method can be used to support the knowledge engineers in designing, building and refining DL ontologies. This method has been implemented in the tool Relexo.