DEA

Représentations implicites en logique propositionnelle

Encadrement

                                    Sylvie Coste-Marquis, maître de conférences
                                    Daniel Le Berre, maître de conférences
                                    Pierre Marquis, professeur

{coste, leberre, marquis}@cril.univ-artois.fr

Laboratoire d'accueil

CRIL/Université d'Artois, EA 2464

Le stage de DEA sera réalisé dans les locaux du CRIL, à Lens.

Sujet de DEA

Motivations

Des travaux récents ont montré l'intérêt pratique des représentations implicites de fragments particuliers de la logique propositionnelle pour la représentation des connaissances. En effet, de telles représentations permettent la prise en compte d'instances dont la taille rend infaisable en pratique toute représentation explicite. Parmi les fragments intéressants figurent ceux regroupant les représentations par impliquants premiers ou impliqués premiers qui autorisent une fois calculées la mise en oeuvre efficace de plusieurs traitements et transformations centraux dans de nombreux problèmes d'intelligence artificielle (en particulier le diagnostic de pannes).

Travail à réaliser

Le travail demandé comporte un volet fondamental et un volet expérimental.
Sur le plan fondamental, il s'agit d'analyser dans quelle mesure la technique des méta-produits proposée par Madre et Coudert pour représenter implicitement des impliquants premiers peut s'étendre à la représentation de certains impliquants / impliqués premiers sur des langages cibles (par exemple, ceux construits sur un sous-langage donné, ceux de longueur limitée par une borne donnée, etc.). Il s'agit aussi de situer les langages de représentation implicite obtenus dans le cadre d'analyse proposé par Darwiche et Marquis (IJCAI'01).
Sur le plan expérimental, il s'agit de comparer l'approche fondée sur les méta-produits avec celle s'appuyant sur une représentation compacte par ZBDDs proposée récemment par Simon et del Val (IJCAI'01).

Bibliographie sommaire

A. Darwiche and P. Marquis. A Perspective on Knowledge Compilation. Proceedings of 17^th International Joint Conference on Artificial Intelligence (IJCAI'01), Seattle (WA), 2001 (175-182).

J.-C. Madre and O. Coudert. Implicit and Incremental Computation of Primes and Essential Primes of Boolean Functions. Proceedings of 29^th DAC, Anaheim (CA), 1992.

P. Marquis. Consequence Finding Algorithms. In Handbook on Defeasible Reasoning and Uncertainty Management Systems, D. Gabbay and Ph. Smets (eds.), Vol. 5 : Algorithms for Defeasible and Uncertain Reasoning, S. Moral and J. Kohlas (eds.), chapter 2, Kluwer Academic Publisher, 2000 (41-145).

L. Simon and A. del Val. Efficient consequence finding. Proceedings of 17^th International Joint Conference on Artificial Intelligence (IJCAI'01), Seattle (WA), 2001 (359-365).

Poursuite en thèse et financement

S'il est bien conduit, le sujet pourra être poursuivi en thèse. Un financement de celle-ci par une allocation du Ministère ou de la Région Nord/Pas-de-Calais est envisageable.