La complexité des relations d'inférence non-monotone dans les approches syntaxiques

National audienceCet article présente différents résultats concernant la complexité des relations d'inférence non-monotone dans quelques approches syntaxiques. A partir d'une base de croyances E (pouvant être inconsistante) et d'un pré-ordre sur E, nous commençons par rappeler différents mécanismes de sélection de sous-ensembles consistants préférés sur E dans un cadre syntaxique. Puis nous présentons quelques principes d'inférence permettant la gestion de ces multiples sous-ensembles. Au croisement de chaque mécanisme de sélection m et de chaque principe d'inférence p, on définit une relation d'inférence non-monotone dont nous étudions la complexité temporelle. Nous fournissons ainsi une synthèse de diverses approches syntaxiques du raisonnement non-monotone. Les résultats obtenus confirment la similarité de ces approches (elles sont toutes de complexités à peu près équivalentes), tout en restant peu encourageants : en effet, toutes nos relations d'inférence non-monotone ont, dans le pire des cas, une complexité largement supérieure à la complexité de d'inférence monotone