Skip to main content Skip to main navigation


Decidable Reasoning in Terminological Knowledge Representation Systems

Martin Buchheit; Francesco M. Donini; Andrea Schaerf
DFKI, DFKI Research Reports (RR), Vol. 93-10, 1993.


Terminological Knowledge Representation Systems (TKRS) are tools for designing and using knowledge bases that make use of terminological languages (or concept languages). We analyze from a theoretical point of view a TKRS whose capabilities go beyond the ones of presently available TKRS. The new features studied, all of practical interest, can be summarized in three main points. First, we consider a highly expressive terminological language, called ALCNR, including general complements of concepts, number restrictions and role conjunction. Second, we allow to express inclusion statements between general concepts, and terminological cycles as a particular case. Third, we prove the decidability of a number of desirable TKRS-deduction services (like satisfiability-, subsumption- and instance checking) through a sound, complete and terminating calculus for reasoning in ALCNR-knowledge bases. Our calculus extends the general technique of constraint systems and can be easily turned into a procedure using exponential space. As a byproduct of the proof, we get also the result that inclusion statements in ALCNR can be simulated by terminological cycles, if descriptive semantics is adopted.