# Computing a Minimal Representation of the Subsumption Lattice of all Conjunctions of Concepts Defined in a Terminology

From International Center for Computational Logic

# Computing a Minimal Representation of the Subsumption Lattice of all Conjunctions of Concepts Defined in a Terminology

##### Franz BaaderFranz Baader

Franz Baader

**Computing a Minimal Representation of the Subsumption Lattice of all Conjunctions of Concepts Defined in a Terminology***Proceedings of the International Symposium on Knowledge Retrieval, Use, and Storage for Efficiency, KRUSE 95*, 168-178, 1995**Kurzfassung****Abstract**

For a given TBox of a terminological KR system, the classification algorithm computes (a representation of) the subsumption hierarchy of all concepts introduced in the TBox. In general, this hierarchy does not contain sufficient information to derive all subsumption relationships between conjunctions of these concepts. We show how a method developed in the area of ``formal concept analysis*for computing minimal implication bases can be used to determine a minimal representation of the subsumption hierarchy between conjunctions of concepts introduced in a TBox. To this purpose, the subsumption algorithm must be extended such that it yields (sufficient information about) a counterexample in cases where there is no subsumption relationship. For the concept language ALC, this additional requirement does not change the worst-case complexity of the subsumption algorithm. One advantage of the extended hierarchy is that it is a lattice, and not just a partial ordering.***Forschungsgruppe:****Research Group:**AutomatentheorieAutomata Theory

```
@inproceedings{ Baader-KRUSE-95,
address = {Santa Cruz, USA},
author = {F. {Baader}},
booktitle = {Proceedings of the International Symposium on Knowledge Retrieval, Use, and Storage for Efficiency, KRUSE 95},
pages = {168--178},
title = {Computing a Minimal Representation of the Subsumption Lattice of all Conjunctions of Concepts Defined in a Terminology},
year = {1995},
}
```