Modifications controlées des implications de la base de Guigues-Duquenne

Nous nous interessons aux implications contenues dans la base de Guigues-Duquenne. Cette base, canonique, a la particularite de posseder un nombre minimum d'implications. Il n'existe pas encore, a notre connaissance, d'algorithmes permettant l'enumeration de ces implications en temps polynomial en prenant comme entree la famille des elements inf-irreductibles d'un systeme de fermeture.

Dans cet expose, nous presentons deux methodes permettant de modifier la donnee de depart (l'ensemble des elements inf-irreductibles) tout en sachant quelles differences existent entre la base de Guigues-Duquenne de la nouvelle donnee et de l'ancienne.

L'objectif est de transformer une donnee initiale R en une donnee R' permettant un calcul "plus simple" de cette base. Une fois la base de Guigues-Duquenne de R' calculee, la base correspondant a R est determinee a partir de celle-ci. Les deux methodes que nous presenterons sont la reduction d'elements clones (jouant des roles symetriques) et la manipulation des implications unitaires (dont la taille du premisse est egale a 1).