A finite basis for the set of EL-implications holding in a finite model

Franz BaaderFranz Baader, Felix DistelFelix Distel

Download

Franz Baader, Felix Distel
A finite basis for the set of EL-implications holding in a finite model
Technical Report, Inst. für Theoretische Informatik, TU Dresden, volume 07-02, 2007

Details
Bibtex

KurzfassungAbstract
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 report 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.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Dist07,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Felix {Distel}},
  institution = {Inst.\ f{\"u}r Theoretische Informatik, TU Dresden},
  number = {07-02},
  title = {A finite basis for the set of {EL}-implications holding in a finite model},
  year = {2007},
}