# A Finite Basis for the Set of EL-Implications Holding in a Finite Model

From International Center for Computational Logic

# A Finite Basis for the Set of EL-Implications Holding in a Finite Model

##### Franz BaaderFranz Baader, Felix DistelFelix Distel

Franz Baader, Felix Distel

In Raoul Medina and Sergei Obiedkov, eds.,

**A Finite Basis for the Set of EL-Implications Holding in a Finite Model**In Raoul Medina and Sergei Obiedkov, eds.,

*Proceedings of the 6th International Conference on Formal Concept Analysis, (ICFCA 2008)*, volume 4933 of Lecture Notes in Artificial Intelligence, 46-61, 2008. Springer**Kurzfassung****Abstract**

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 emph{finite} set of implications (GCIs) holding in this model from which all implications (GCIs) holding in the model follow.**Forschungsgruppe:****Research Group:**Automatentheorie

```
@inproceedings{ BaaderDistel08,
author = {Franz {Baader} and Felix {Distel}},
booktitle = {Proceedings of the 6th International Conference on Formal Concept Analysis, (ICFCA 2008)},
editor = {Raoul {Medina} and Sergei {Obiedkov}},
pages = {46--61},
publisher = {Springer},
series = {Lecture Notes in Artificial Intelligence},
title = {A Finite Basis for the Set of {EL}-Implications Holding in a Finite Model},
volume = {4933},
year = {2008},
}
```