A Description Logic with Transitive and Inverse Roles and Role Hierarchies

From International Center for Computational Logic

Toggle side column

A Description Logic with Transitive and Inverse Roles and Role Hierarchies

Ian HorrocksIan Horrocks,  Ulrike SattlerUlrike Sattler
A Description Logic with Transitive and Inverse Roles and Role Hierarchies


Ian Horrocks, Ulrike Sattler
A Description Logic with Transitive and Inverse Roles and Role Hierarchies
Journal of Logic and Computation, 9(3):385-410, 1999
  • KurzfassungAbstract
    The combination of transitive and inverse roles is important in a range of applications, and is crucial for the adequate representation of aggregated objects, allowing the simultaneous description of parts by means of the whole to which they belong and of wholes by means of their constituent parts. In this paper we present tableaux algorithms for deciding concept satisfiability and subsumption in Description Logics that extend alc with both transitive and inverse roles, a role hierarchy, and functional restrictions. In contrast to earlier algorithms for similar logics, those presented here are well-suited for implementation purposes: using transitive roles and role hierarchies in place of the transitive closure of roles enables sophisticated blocking techniques to be used in place of the cut rule, a rule whose high degree of non-determinism strongly discourages its use in an implementation. As well as promising superior computational behaviour, this new approach is shown to be sufficiently powerful to allow subsumption and satisfiability with respect to a (possibly cyclic) knowledge base to be reduced to concept subsumption and satisfiability, and to support reasoning in a Description Logic that no longer has the finite model property.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@article{ HorrSat-JLC-99,
  author = {I. {Horrocks} and U. {Sattler}},
  journal = {Journal of Logic and Computation},
  number = {3},
  pages = {385--410},
  title = {A Description Logic with Transitive and Inverse Roles and Role Hierarchies},
  volume = {9},
  year = {1999},
}