Algorithm Design

A key strand of the Camelot project is the design of new algorithms for reasoning in very expressive description logics: logics that include at least transitive closure, and a hierarchy of roles. The use of transitive roles, rather than a transitive closure operator, is crucial as it facilitates the development of highly optimised and empirically tractable implementations. This point is covered in more detail by a presentation which compares and contrasts the two approaches. (132Kb compressed postscript)

Recently, expressive power has been augmented by the addition of functional and inverse (converse) roles and general cardinality restrictions on roles.

Details of several of these algorithms can be found in:

I. Horrocks, U. Sattler, and S. Tobies. Practical reasoning for expressive description logics. In H. Ganzinger, D. McAllester, and A. Voronkov, editors, Proceedings of the 6th International Conference on Logic for Programming and Automated Reasoning (LPAR'99), number 1705 in Lecture Notes in Artificial Intelligence, pages 161-180. Springer-Verlag, 1999.
BibTeX entry, Compressed PS

Back to the Camelot home page.