next up previous
Next: Introduction

Research Note: New Polynomial Classes for Logic-Based Abduction

Bruno Zanuttini (

GREYC, Université de Caen, Boulevard du Maréchal Juin, 14032 Caen Cédex, France


We address the problem of propositional logic-based abduction, i.e., the problem of searching for a best explanation for a given propositional observation according to a given propositional knowledge base. We give a general algorithm, based on the notion of projection; then we study restrictions over the representations of the knowledge base and of the query, and find new polynomial classes of abduction problems.

Bruno Zanuttini 2003-06-30