Expressive Number Restrictions in Description Logics

F. BaaderF. Baader, U. SattlerU. Sattler

Datei:BaaderSattler-JLC-99.ps.gz

Download

F. Baader, U. Sattler
Expressive Number Restrictions in Description Logics
Journal of Logic and Computation, 9(3):319--350, 1999

Details
Bibtex

KurzfassungAbstract
Number restrictions are concept constructors that are available in

 almost all implemented Description Logic systems. However, they are mostly
 available only in a rather weak form, which considerably restricts their
 expressive power. 
 
 On the one hand, the roles that may occur in number restrictions are usually
 of a very restricted type, namely atomic roles or complex roles built using
 either intersection or inversion. In the present paper, we increase the expressive power
 of Description Logics by allowing for more complex roles in number
 restrictions. As role constructors, we consider composition of roles (which
 will be present in all our logics) and intersection, union, and inversion
 of roles in different combinations. We will present two decidability results
 (for the basic logic that extends ALC by number restrictions on roles
 with composition, and for one extension of this logic), and three
 undecidability results for three other extensions of the basic logic.
 
 On the other hand, with the rather weak form of number restrictions available
 in implemented systems, the number of role successors of an individual can
 only be restricted by a fixed non-negative integer.  To overcome this lack of
 expressiveness, we allow for variables ranging over the non-negative integers
 in place of the fixed numbers in number restrictions. The expressive power of
 this constructor is increased even further by introducing explicit quantifiers
 for the numerical variables. The Description Logic obtained this way turns out
 to have an undecidable satisfiability problem. For a restricted logic we show

that concept satisfiability is decidable.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ BaaderSattler-JLC-99,
  author = {F. {Baader} and U. {Sattler}},
  journal = {Journal of Logic and Computation},
  number = {3},
  pages = {319--350},
  title = {Expressive Number Restrictions in Description Logics},
  volume = {9},
  year = {1999},
}