On se donne une hiérarchie de types
simples, partiellement ordonnée par la relation ≤ dite relation de
spécialisation, et un ensemble de déclarations d'incompatibilités entre
types (cf. définitions dans
chapitre SG). On appelle type conjonctif un ensemble de types simples deux à
deux incomparables. Un type conjonctif s'obtient à partir d'un ensemble de types
en ne gardant que les types les plus spécialisés. Par exemple, à partir de
l'ensemble {EntitéMobile, EntitéSousMarine, Poisson, Animal} avec
EntitéSousMarine ≤ EntitéMobile, Poisson ≤ Animal,
Poisson ≤ EntitéSousMarine, on obtient le type conjonctif
{Poisson}.
La relation de spécialisation est étendue aux types conjonctifs de la façon suivante :
étant donnés deux types
conjonctifs t = {t_1 ... t_n} et s = {s_1 ...
s_p}, t ≤ s si pour tout s_j il existe un
t_i tel que t_i ≤ s_j.
Autrement dit, t
est une spécialisation de s, si tout type simple de s
est spécialisé dans t. Par exemple, {Poisson,
EntitéDeCouleurRouge} est une spécialisation de {Poisson}
ainsi que de {Animal, EntitéSousMarine}.
Les problèmes de base que l'on veut résoudre sont les suivants :
Problème 1 (calcul d'un type
conjonctif) : étant donné un ensemble t de types simples,
calculer le
type conjonctif associé à t (donc garder les minimaux de t)
Problème 2 (comparaison de types conjonctifs) : Etant donnés deux types conjonctifs t et s, a-t-on t ≤ s?
Problème 3 (acceptabilité d'un type
conjonctif) : Etant donné un type conjonctif t, t est-il acceptable
(ne
contient pas une spécialisation de deux types incompatibles)
Problème 4 (borne inférieure) :
Etant donnés deux types conjonctifs t et s,
calculer la borne inférieure de
t et s (la spécialisation de t et s la plus générale)
Problème 5 (borne supérieure) :
Etant donnés deux types conjonctifs t et s,
calculer la borne supérieure de
t et s (la généralisation de t et s la plus spécifique).
L'ensemble des types conjonctifs que l'on peut construire à partir d'une hiérarchie de types simples a une taille exponentielle en la taille de la hiérarchie. Il n'est donc pas envisageable de représenter l'ensemble des types conjonctifs en extension. Le problème consiste alors à trouver une façon de représenter la hiérarchie des types simples ainsi que les incompatibilités de types, de façon à pouvoir résoudre efficacement les problèmes de base décrits ci-dessus.
Le travail partira d'un chapitre d'une thèse décrivant différentes méthodes de codage d'ordres partiels (Thèse de E. Thierry, "Sur quelques interactions entre structures de données et algorithmes efficaces pour les ordres et les graphes", 2001). Il s'agira de choisir une méthode, de l'adapter, puis de l'implémenter.
Le résultat devra être intégré à la plate-forme CoGITaNT (une plate-forme C++ de développement d'applications à base de graphes conceptuels http://cogitant.sourceforge.net/).
Enfin, on pourra alors s'intéresser à l'introduction de types disjonctifs et à l'utilisation du codage proposé pour traiter de tels types.