Une introduction aux logiques de description

Ce document est une adaptation du chapitre 4 de :
Fournier-Viger, Philippe (2005) "Un modèle de représentation des connaissances à trois niveaux de sémantique pour les systèmes tutoriels intelligents". Mémoire de maîtrise (M.Sc.), Université de Sherbrooke, Sherbrooke, Canada.

Attention: Si vous copiez du texte de cette page Web pour l'inclure dans un de vos documents, vous devez citer correctement le mémoire de master ci-dessus. Quatre personnes ont déjà plagié cette page Web dans trois thèses de doctorat et un mémoire de master. Avec Internet, il est facile de détecter le plagiat. -- Philippe, mai 2011

Ce document est seulement mis à jour pour corriger les erreurs. Vous pouvez me contacter pour rapporter des erreurs.

--------------------------------------------------

Ce document présente les logiques de description (LD), une famille de langages de représentation de connaissances qui exploitent, en général, des sous-ensembles décidables (pour une logique, un problème de raisonnement est décidable si une machine de Turing peut le résoudre en un nombre fini d'étapes) de la logique de premier ordre. Ils ont été largement étudiés et utilisés dans plusieurs systèmes à base de connaissances (Nardi et Brachman, 2003). Cinq sections forment ce chapitre : la section 1.1 met en contexte les LD, la section 1.2 présente les notions de base des LD avec un exemple, la section 1.3 décrit la sémantique formelle de la logique minimale AL et de ses extensions les plus courantes, la section 1.4 aborde les services d'inférence usuels pour les LD et compare les principaux moteurs d'inférence.

1.1 Le contexte

L'accent au sein des LD est mis sur les services de raisonnement et plus particulièrement sur ceux pour la prise de décision : l'objectif principal des LD consiste à pouvoir raisonner efficacement pour minimiser les temps de réponse. Par conséquent, la communauté scientifique a publié de nombreuses recherches qui portent sur l'étude du rapport expressivité/performance des différentes LD (Nardi et Brachman, 2003). La principale qualité des LD réside dans leurs algorithmes d'inférence dont la complexité est souvent inférieure aux complexités des démonstrateurs de preuves de la logique de premier ordre (Tsarkov et Horrocks, 2003).

1.1.1 Une approche ontologique

Les LD utilisent une approche ontologique, c'est-à-dire que pour décrire les individus d'un domaine, elles requièrent tout d'abord la définition des catégories générales d'individus et les relations logiques que les individus ou catégories peuvent entretenir entre eux. Cette approche ontologique est naturelle pour le raisonnement puisque même si la majorité des interactions se déroule au niveau des individus, la plus grande partie du raisonnement se produit au niveau des catégories (Russell et Norvig, 2002).

1.1.2 Un historique des logique de description

Le développement des LD fut fortement influencé par les travaux sur la logique des prédicats, les schémas (frames) (Minsky, 1981), les réseaux sémantiques et Prolog. Des correspondances existent entre les LD et ces formalismes (Sattler et al., 2003; Baader et Nutt, 2003). La présence de catégories générales d'objets et de relations fait d'ailleurs partie de l'héritage conceptuel des schémas et des réseaux sémantiques.

La première génération de logiques de description (1980 - 1990)

Les premiers travaux sur les LD commencèrent au début des années 1980 avec des systèmes à base de connaissances tels que KL-ONE, BACK et LOOM (Baader et al., 2003; Nardi et Brachman, 2003). Ces premières implantations résolvent des problèmes d'inférence en temps souvent polynomial, par le biais d'une catégorie d'algorithmes de vérification de subsomption de type normalisation/comparaison (structural subsumption algorithmes). Ces algorithmes ne s'appliquent qu'à des LD peu expressives, sans quoi ils sont incomplets, c'est-à-dire qu'ils sont incapables de prouver certaines formules vraies.

La deuxième génération de logiques de description (1990 - aujourd'hui)

Dans les années 1990, une nouvelle classe d'algorithmes est apparue : les algorithmes de vérification de satisfaisabilité à base de tableaux (tableau-based algoritdms). Ces derniers raisonnent sur des LD dites expressives ou très expressives, mais en temps exponentiel. Cependant, en pratique, le comportement des algorithmes est souvent acceptable (Baader et al., 2003). L'expressivité accrue a ouvert la porte à de nouvelles applications telles que le Web sémantique (Baader et al., 2003; Zou et al., 2004; Horrocks et al., 2003). Le terme logiques de description expressives (LDE) désigne l'ensemble des LD qui ont émergé pendant cette période.

1.2 Les deux niveaux de description

La modélisation des connaissances d'un domaine avec les LD se réalise en deux niveaux. Le premier, le niveau terminologique ou TBox, décrit les connaissances générales d'un domaine alors que le second, le niveau factuel ou ABox, représente une configuration précise. Une TBox comprend la définition des concepts et des rôles, alors qu'une ABox décrit les individus en les nommant et en spécifiant en terme de concepts et de rôles, des assertions qui portent sur ces individus nommés. Plusieurs ABox peuvent être associés à une même TBox ; chacune représente une configuration constituée d'individus, et utilise les concepts et rôles de la TBox pour l'exprimer.

1.2.1 Le niveau terminologique (TBox)

Le coté gauche du tableau 1.1 présente un exemple de TBox. Les prochains paragraphes explicitent divers aspects des TBox en se référant à cet exemple.

Tableau 1.1 Une base de connaissances composée d'une TBox et d'une ABox

Les entités atomiques

Les concepts atomiques et rôles atomiques constituent les entités élémentaires d'une TBox. Les noms débutant par une lettre majuscule désignent les concepts, alors que ceux débutant par une lettre minuscule dénomment les rôles (par exemple : les concepts Femelle, Mâle, Homme et Femme, et le rôle relationParentEnfant).

Les concepts et rôles atomiques prédénis

Les LD prédénissent minimalement quatre concepts atomiques : le concept et le rôle , les plus généraux de leur catégorie respective, et le concept ainsi que le rôle les plus spécifiques (c'est-à-dire l'ensemble vide).

Les entités composées

Les concepts et rôles atomiques peuvent être combinés au moyen de constructeurs pour former respectivement des concepts et des rôles composés. Par exemple, le concept composé MâleFemelle résulte de l'application du constructeur aux concepts atomiques Mâle et Femelle. Le concept Mâle Femelle s'interprête comme l'ensemble des individus qui appartiennent aux concepts Mâle et Femelle. Les différentes LD se distinguent par les constructeurs qu'elles proposent. Plus les LD sont expressives, plus les chances sont grandes que les problèmes d'inférence soient non décidables ou de complexité très élevée. Par contre, les LD trop peu expressives démontrent une inaptitude à représenter des domaines complexes.

La notation

La suite de ce document adopte la notation suivante : R dénote un rôle, C,D des concepts composés et A,B des concepts atomiques.

La notion d'interprétation

Expliciter formellement la sémantique d'une TBox, requiert de définir préalablement la notion d'interprétation. Une interprétation se compose d'un domaine d'interprétation et d'une fonction d'interprétation . Le domaine d'interprétation consiste en un ensemble d'individus. La fonction d'interprétation assigne à chaque concept atomique A un ensemble tel que A , et à chaque rôle atomique R une relation binaire R ×.

La définition formelle de TBox

Une TBox contient des axiomes terminologiques de la forme C D ou C D. La première sert à énoncer des relations d'équivalence entre concepts, alors que la seconde permet d'exprimer des relations d'inclusion. Une interprétation I satisfait un axiome C D si et seulement si C D. Une interprétation I satisfait un axiome C D si et seulement si C = D.

Une interprétation satisfait une TBox (est un modèle de TBox) si et seulement si l'interprétation satisfait tous les axiomes de la TBox.

La section 1.3 décrit la sémantique des différents constructeurs utilisés dans la TBox de l'exemple.

1.2.2 Le niveau factuel (ABox)

Une ABox contient un ensemble d'assertions sur les individus : (1) des assertions d'appartenance et (2) des assertions de rôle. Chaque ABox doit être associée à une TBox, car les assertions s'expriment en terme des concepts et des rôles de la TBox. La partie droite du tableau 1.1 illustre un exemple d'ABox.

Une ABox désigne des individus dans ses assertions par des noms qu'elle leur donne. Ce texte utilise le terme individu nommé (nominal ou individual name, en anglais) pour référer à ces noms. L'exemple du tableau 1.1 comprend les individus nommés suivants : Anne, David, Robert et Sophie. La suite de ce texte représente par les lettres a, b les individus nommés. Une fonction d'interprétation assigne à chacun de ces noms a, un individu a tel que a . Les moteurs d'inférence pour LD adoptent généralement l'hypothèse de noms uniques (HNU), c'est-à-dire que pour tout individu nommé a et b, a b (Baader et Nutt, 2003).

Chaque assertion d'appartenance d'une ABox (notée C(a)), déclare que pour cette ABox, il existe un individu nommé a, membre du concept C de la TBox associée. Une interprétation satisfait une assertion d'appartenance C(a) si et seulement si a C.

Une assertion de rôle, de la forme R(a, b) indique que pour cette ABox, il existe un individu nommé a qui est en relation avec un individu nommé b par le rôle R (défini dans la TBox associée), tel que a fait partie du domaine de R et b fait partie de l'image. Une interprétation satisfait une assertion de rôle R(a, b) si et seulement si (a, b) R.

Finalement, une interprétation satisfait une ABox A (est un modèle d'ABox) si et seulement si satisfait toutes les assertions de A.

1.3 La logique minimale

Pour des fins de simplicité, ce document décrit en premier lieu une logique minimale nommée qui a été introduite par Schmidt-Schaub et Smolka (1991) et qui revêt d'une grande importance dans le domaine. Cette logique est minimale, dans le sens où une logique moins expressive représente peu d'intérêt (Baader et Nutt, 2003).

1.3.1 Les constructeurs d'

La figure 1.1 illustre les constructeurs offerts par pour l'édification de concepts composés.

Figure 1.1 La grammaire des expressions conceptuelles selon

Le constructeur C D permet de faire la conjonction de deux concepts composés, ce qui représente l'ensemble des individus, membres à la fois du concept C et du concept D pour une interprétation. Le constructeur A est utilisé pour évoquer la négation d'un concept atomique, c'est-à-dire les individus pour une interprétation qui n'appartiennent pas au concept atomique A.

Le quantificateur existentiel non typé R. désigne l'ensemble des individus, membres du domaine d'un rôle R pour une interprétation donnée. Par exemple, pour une interprétation qui est un modèle de l'ABox et de la TBox du tableau 1.1, relationParentEnfant. équivaut l'ensemble des individus {Sophie, Robert}.

Le quantificateur universel R.C évoque l'ensemble des individus du domaine d'un rôle R qui sont en relation, par le biais de R, avec un individu du concept C, pour une interprétation donnée. Par exemple, pour une interprétation I qui est un modèle de l'ABox et de la TBox du tableau 1.1, relationParentEnfant.Homme équivaut l'ensemble des individus {Robert}.

ne permet pas la spécification de rôles à l'aide de constructeurs (rôles composés). La sous-section qui suit décrit la sémantique formelle d'.

1.3.2 La sémantique formelle d'

Figure 1.2 La sémantique formelle d'

Afin de supporter la notion de concepts composés, la fonction d'interprétation est étendue par les règles décrites à la figure 1.2. Deux concepts C et D d'une TBox s'équivalent si et seulement si C = D pour toute interprétation modèle de .

L'interprétation selon l'hypothèse de monde ouvert

Dans les LD, l'interprétation des connaissances respecte l'hypothèse du monde ouvert. Contrairement à la sémantique des bases de données traditionnelles, l'absence d'information représente l'ignorance plutôt qu'une information négative. Pour enrichir la comparaison avec les bases de données, répondre à une requête pour un système bâti sur les LD nécessite d'effectuer un raisonnement logique souvent plus complexe qu'une simple recherche pour vérifier la présence d'une information, car le système doit souvent considérer plusieurs interprétations possibles, une conséquence de l'hypothèse du monde ouvert (Baader et al., 2003).

La correspondance entre et la logique des prédicats

Figure 1.3 Correspondance entre les constructeurs d' et la logique des prédicats

Une correspondance existe entre la logique et la logique de premier ordre (Baader et Nutt, 2003). Un concept atomique A correspond à un prédicat unaire, un rôle R à un prédicat binaire , un individu correspond à une constante et un concept composé à une formule à une variable libre . La figure 1.3 illustre la façon de traduire les constructeurs d' en leur équivalent en logique des prédicats.

1.3.2 Les extensions d'

Il existe trois façons proéminentes d'étendre : (1) ajouter des constructeurs de concepts, (2) ajouter des constructeurs de rôles et (3) énoncer des contraintes sur l'interprétation des rôles (Baader, 2003).

L'extension par ajout de constructeurs de concepts ou de rôles

Le tableau 1.2 illustre des exemples de constructeurs pour augmenter (Baader, 2003). La première colonne contient la lettre qui désigne le constructeur, la deuxième sa syntaxe d'utilisation et la dernière sa sémantique. La nomenclature des LD dicte que pour chaque constructeur ajouté, il faut agglutiner la lettre correspondante au nom de la logique originale. Par exemple, la logique , enrichie de l'union () et de la quantification existentielle complète (), se nomme . Il faut noter que l'appelation équivaut à , puisque l'union et la quantification existentielle complète s'expriment par la négation complète et inversement, car CD (CD) et R.C R.C (Baader et Nutt, 2003).

Tableau 1.2 Exemple de constructeurs de rôles et concepts pour étendre

Le constructeur permet la description de concepts par l'énumération d'individus nommés, désigne l'union de concepts arbitraires, la quantification existentielle complète, la négation complète, les rôles inverses et l'inclusion entre rôles. Les constructeurs , et sont trois variantes de la contrainte de cardinalité sur rôle.

L'extension par ajout de contraintes sur l'interprétation des rôles

La spécification d'un ensemble de rôles transitifs , constitue une extension par ajout de contraintes sur l'interprétation des rôles (désignée par la lettre ), qui permet l'expression de rôles transitifs tels qu'ancêtreDe ou frèreDe (Baader, 2003). La lettre désigne la logique additionnée de .

L'extension des types primitifs ()

Une dernière extension, symbolisée par la lettre (), ajoute le support des types primitifs (Horrocks et al., 2003). Cette extension augmente d'un second domaine d'interprétation disjoint avec et qui représente l'ensemble des valeurs de type primitif. Le domaine définit plusieurs sous-domaines tels que les entiers, les chaînes de caractères, les entiers positifs, etc. Les éléments de ces domaines se nomment individus primitifs. De plus, l'extension ajoute un nouveau type de rôle, défini comme une relation binaire sur × et appelé rôles à valeurs primitives. La lettre U représente l'ensemble de ces rôles. Cet ajout autorise la spécification d'assertions de rôle telles que u(a, 205006007) et v(a, ”Jean Jacques”) où u, v U.

Quoiqu'il soit possible de définir un constructeur de hiérarchies pour ces rôles (par exemple : u v avec la sémantique u v), plusieurs constructeurs pour rôle classique tels que le constructeur de rôle transitif et le constructeur de rôle inverse n'ont pas leur équivalent pour les rôles à valeurs primitives.

1.4 L'inférence

L'inférence s'effectue au niveau terminologique ou factuel. Les sections 1.4.1 et 1.4.2 abordent le raisonnement au niveau terminologique et factuel, respectivement. Pour terminer, la section 1.4.3 présente un tableau comparatif des différents moteurs d'inférence.

1.4.1 L'inférence au niveau terminologique

Quatre principaux problèmes d'inférence se présentent au niveau terminologique ( Baader et Nutt, 2003) :

• Satisfaisabilité : Un concept C d'une terminologie est satisfaisable si et seulement existe un modèle de tel que C .
• Subsomption : Un concept C est subsumé par un concept D pour une terminologie si et seulement si C D pour tout modèle de .
• Équivalence : Un concept C est équivalent à un concept D pour une terminologie et seulement si C D pour chaque modèle de .
• Disjonction (disjointness) : Des concepts C et D sont disjoints par rapport terminologie
  si et seulement si C \ D = ; pour chaque modèle de .

Les moteurs d'inférence actuels tirent généralement profit du fait que les quatre types de problèmes d'inférence peuvent être réduits à des problèmes de subsomption ou à des problèmes de satisfaisabilité. Les figures 1.4 et 1.5 illustrent cette propriété qui implique, que les moteurs d'inférence des LD ne nécessitent souvent qu'un seul algorithme d'inférence pour raisonner au niveau terminologique (Baader et Nutt, 2003). D'ailleurs, les deux grandes classes d'algorithmes de raisonnement pour les LD (algorithmes de subsomption de type normalisation/comparaison et algorithmes de vérification de satisfaisabilité à base de tableaux) correspondent aux façons de réduire respectivement des problèmes d'inférence à des problèmes de subsomption et de satisfaisabilité (Baader et al., 2003).

Figure 1.4 Réduction des problèmes d'inférence d'une TBox à des problèmes de subsomption
Figure 1.5 Réduction des problèmes d'inférence d'une TBox à des problèmes de satisfaisabilité

Tableau 1.3 Complexité de la vérification de la subsomption et de la satisfaisabilité en fonction de l'expressivité des LD

Le tableau 1.3 présente un aperçu non exhaustif de la complexité du raisonnement au niveau terminologique en fonction de l'expressivité (Donini, 2003; Baader et al., 2003; Horrocks et Sattler, 2005). Ce tableau met en évidence la connaissance pointue des LD que la communauté scientifique détient. Les classes de complexité énumérées dans le tableau proviennent de la théorie de la complexité informatique. Voici une définition de ces classes (Padadimitriou, 1994) :

• P: la classe des problèmes de décision (un problème de décision prend en entrée un énoncé de problème et produit en sortie une réponse
  positive ou négative: oui ou non). qui requièrent un temps polynomial par rapport à la taille du problème pour obtenir une solution avec une machine de Turing déterministe.
• NP: la classe des problèmes qui nécessitent un temps polynomial pour trouver une solution avec une machine de Turing non déterministe.
• PSpace : la classe des problèmes de décision qui requièrent une quantité de mémoire polynomiale pour résoudre un problème avec une machine de Turing déterministe ou non déterministe.
• ExpTime : la classe des problèmes de décision solubles par une machine de Turing déterministe en un temps où est une fonction polynomiale de n, la taille du problème.
• NExpTime : la classe des problèmes de décision solubles par une machine de Turing non-déterministe en un temps où est une fonction polynomiale de n, la taille du problème.

Il est connu que P NP PSpace ExpTime NExpTime (Padadimitriou, 1994).

1.4.2 L'inférence au niveau factuel

Le niveau factuel comprend quatre principaux problèmes d'inférence (Baader et Nutt, 2003) :

• Cohérence : Une ABox A est cohérente par rapport à une TBox si et seulement s'il existe un modèle de A et ).
• Vérification d'instance : Vérifier par inférence si une assertion C(a) est vraie pour tout modèle d'une ABox A et d'une TBox .
• Vérification de rôle : Vérifier par inférence si une assertion R(a, b) est vraie pour tout modèle d'une ABox A et d'une TBox .
• Problème de récupération : Pour une ABox A, un concept C d'une terminologie , inférer les individus a1 ...an CI pour tout modèle de .

Les moteurs d'inférence

Le tableau 1.4 dresse une comparaison des principaux moteurs d'inférence pour les LDE (logiques de description expressives, cf. section 1.1.2) : FaCT (Horrocks, 1998), Racer (Haarslev et Möller, 2001), Pellet (Sirin et Parsia, 2004), FaCT++ (Tsarkov et Horrocks, 2004), F-OWL (Zou et al., 2004), Surnia, et Hoolet. Le critère "Mise-à-échelle" mesure la capacité à demeurer efficace proportionnellement à la complexification des ontologies. Le tableau reprend les données de Zou et al. (2004) pour ce critère, celui de décidabilité et pour les caractéristiques de Hoolet, Surnia et F-OWL. Ce document ne traitera pas du critère "OWL" dans le tableau 1.4.

Tableau 1.4 Tableau comparatif des principaux moteurs d'inférence pour LD

Le raisonnement sur TBox ou ABox

Tous ces moteurs raisonnent autant sur des ABox que sur des TBox, mis à part FaCT et FaCT++ qui se spécialisent en raisonnant sur des TBox seulement. FaCT++ est une variante de FaCT implantée en C++ pour une efficacité accrue, et avec quelques ajouts et différences tels que le tableau l'illustre.

L'expressivité et l'efficacité des moteurs d'inférence

Les moteurs F-OWL, Hoolet et Surnia raisonnent sur des logiques de description très expressives. Hoolet et Surnia raisonnent sur l'expressivité totale de la logique des prédicats, alors que F-OWL infère sur la logique et sur l'expressivité totale de RDF (Ressource Description Framework, un modèle RDF représente
un domaine par un ensemble de triplets sujet, prédicat, valeur qui lient par des propriétés (prédicat) des ressources entre elles (sujet, valeur)).Ces trois moteurs se basent sur des méthodes expérimentales de raisonnement qui exhibent des performances intéressantes pour des problèmes simples, mais insuffisantes pour une utilisation industrielle, en raison de leur faible efficacité et de la non-décidabilité de leurs algorithmes. Ce texte les mentionne à titre informatif.

Comme l'indique le critère "Mise-à-échelle" dans le tableau, les moteurs les plus performants actuellement sont Racer, FaCT, FaCT++ et Pellet. FaCT, FaCT++ et Racer disposent probablement de la plus grande notoriété actuellement, chacun d'eux utilisé dans de nombreux projets. Le moteur Pellet est beaucoup plus récent que les autres et encore en développement. Il échoue à atteindre le niveau de performance de FaCT et Racer (Sirin et Parsia, 2004).

Le fonctionnement de Racer en grappe de calcul

Racer se présente comme un logiciel serveur avec lequel l'interaction a lieu par communication réseau. Racer offre également de fonctionner sous forme de grappe de calcul grâce à RacerProxy (http ://www.sts.tu-harburg.de/ r.f.moeller/racer/). Cet aspect confère un avantage pour Racer. En effet, que le serveur de raisonnement soit distant ou en grappe de calcul facilite la gestion de fortes demandes.

Les services offerts

D'après des tests réalisés pour ce texte avec la version 1.7.23 de Racer, ce dernier accuse un manque de fonctionnalité pour modifier une base de connaissances en mémoire et un manque de certains services de raisonnement. Par exemple, Racer supporte les rôles à valeur primitive, mais ne propose pas de méthode pour en ajouter de nouveaux ou en supprimer dans une base de connaissances chargée en mémoire. Pellet, quoique moins rapide, offre davantage de services pour raisonner et modifier une base de connaissances, selon des essais avec la version 1.1.0. L'auteur de ce document a omis volontairement de tester les moteurs FaCT et FaCT++, car ils ne raisonnent pas au niveau ABox, un aspect essentiel pour le projet de l'auteur

L'interface de communication DIG

Racer, FaCT et FaCT++ se conforment à DIG (Bechhofer et al., 2003), un protocole standard pour interroger un moteur d'inférence par des requêtes HTTP (http ://www.w3.org/Protocols/). DIG vise à faciliter la substitution d'un moteur d'inférence par un autre. Ce protocole se base sur le langage . Certains auteurs proposent un api Java pour communiquer par DIG (http ://dig.sourceforge.net/). Toutefois, DIG comporte un lot considérable de problèmes (Dickinson, 2004) : (1) une documentation pauvre, incomplète pour certains aspects tels que les codes d'erreurs et les réponses aux requêtes, (2) un manque de régularité dans la nomination des entités, (3) des tests de conformité inexistants, (4) un non support de certains services de raisonnement tels que vérifier l'égalité d'individus nommés dans le cas où l'hypothèse de nom unique (HNU) ne tient pas et (5) peu de moteurs d'inférence se conforment à DIG actuellement.

Les interfaces de programmation Java

La plupart des moteurs mentionnés dans cette section procurent une interface de programmation (API) (autre qu'une interface DIG) pour faciliter l'accessibilité par un programme Java (voir le tableau). Ce critère importe particulièrement puisque DIG comporte plusieurs problèmes.

Bibliographie

Baader, F., 2003. Appendix 1 : Description logic terminology. Dans Baader, F., Calvanese, D., McGuinness, D., Nardi, D. et Patel-Schneider, P. (éditeurs), The Description Logic Handbook : Theory, Implementation and Applications. Cambridge University Press, pp. 495505.

Baader, F., Horrocks, I. et Sattler, U., 2003. Description logics as ontology languages for the semantic web. Dans Hutter, D. et Stephan, W. (éditeurs), Festschrift in honor of Jörg Siekmann. Lecture Notes in Articial Intelligence. Springer-Verlag.

Baader, F. et Nutt, W., 2003. Basic description logics. Dans Baader, F., Calvanese, D., McGuinness, D., Nardi, D. et Patel-Schneider, P. (éditeurs), The Description Logic Handbook : Theory, Implementation and Applications. Cambridge University Press, pp. 47100.

Bechhofer, S., Möller, R. et Crowther, P., 2003. The dig description logic interface. Dans Proc. of the 2003 Description Logic Workshop (DL 2003).

Bergamaschi, S., Lodi, S. et Sartori, C., 1994. Description logics as core of a tutoring system. Dans Proc. of the 1994 Description Logic Workshop (DL 94). pp. 7374 .

Dickinson, I., 2004. Implementation experience with the dig 1.1 specication. Rapport technique HPL-2004-85, Digital Media Systems Laboratory, Hewlett-Packard, Bristol.

Donini, F. M., 2003. Complexity of reasoning. Dans Baader, F., Calvanese, D., McGuin ness, D., Nardi, D. et Patel-Schneider, P. (éditeurs), The Description Logic Handbook : Theory, Implementation and Applications. Cambridge University Press, pp. 101141.

Haarslev, V. et Möller, R., Août 2001. Description of the racer system and its applications. Dans Proceedings of the International Workshop on Description Logics (DL-2001). Stanford, Californie, pp. 132141.

Horrocks, I., 1998. The FaCT system. Dans de Swart, H. (éditeur), Automated Reasoning with Analytic Tableaux and Related Methods : International Conference Tableaux'98, number 1397 in Lecture Notes in Articial Intelligence. Springer-Verlag, pp. 307312.

Horrocks, I., Patel-Schneider, P. F. et van Harmelen, F., 2003. From shiq and rdf to owl : The making of a web ontology language. J. of Web Semantics 1 (1), 726.

Horrocks, I. et Sattler, U., 2005. A tableaux decision procedure for SHOIQ. Dans Proc. of the 19th Int. Joint Conf. on Articial Intelligence (IJCAI 2005).

Krdzavac, N., Gasevic, D. et Devedzic, V., 2004. Description logics reasoning in web- based education environments. Dans Proceedings of the Adaptive Hypermedia and Collaborative Web-based Systems (AHCW04). Munich, Allemagne.

Minsky, M., 1981. A framework for representing knowledge. Dans Haugeland, J. (éditeur), Mind Design. The MIT Press, pp. 95128.

Nardi, D. et Brachman, R. J., 2003. An introduction to description logics. Dans Baader, F., Calvanese, D., McGuinness, D., Nardi, D. et Patel-Schneider, P. (éditeurs), The Description Logic Handbook : Theory, Implementation and Applications. Cambridge University Press, pp. 544.

Padadimitriou, C. H., 1994. Computational complexity. Addison-Wesley Publishing Company, Massachusetts, É.-U.

Russell, S. J. et Norvig, P., 2002. Articial Intelligence : A Modern Approach, 2ième édition. Prentice Hall.

Sattler, U., Calvanese, D. et Molitor, R., 2003. Relationships with other formalisms. Dans Baader, F., Calvanese, D., McGuinness, D., Nardi, D. et Patel-Schneider, P. (éditeurs), The Description Logic Handbook : Theory, Implementation and Applications. Cambridge University Press, pp. 142183.

Schmidt-Schaub, M. et Smolka, G., 1991. Attributive concept descriptions with complements. Articial Intelligence 48 (1), 126.

Sirin, E. et Parsia, B., 2004. Pellet : An owl dl reasoner. Dans Haarslev, V. et Möller, R. (éditeurs), Proceedings of the International Workshop on Description Logics (DL2004).

Teege, G., 1994. Using description logics in intelligent tutoring systems. Dans Proc. of the 1994 Description Logic Workshop (DL 94). pp. 7578.

Tsarkov, D. et Horrocks, I., 2003. DL reasoner vs. rst-order prover. Dans Proc. of the 2003 Description Logic Workshop (DL 2003) volume. pp. 152159.

Tsarkov, D. et Horrocks, I., 2004. Ecient reasoning with range and domain constraints. Dans Proc. of the 2004 Description Logic Workshop (DL 2004). pp. 4150.

Zou, Y., Finin, T. et Chen, H., 2004. F-owl : an inference engine for semantic web. Dans Third NASA-Goddard/IEEE Workshop on Formal Approaches to Agent-Based Systems. Greenbelt, Maryland.