ECAI 2004 Conference Paper

A Uniform Tableaux-based Method for Abduction and Contraction in Description Logics

Simona Colucci, Tommaso Di Noia, Eugenio Di Sciascio, Francesco M Donini, Marina Mongiello

We present algorithms for Concept Abduction and Concept Contraction, two reasoning services in Description Logics (DL) recently proposed to model how several supplies fit a demand (all described by concepts), and vice versa, in e-commerce. Our method is based on truth-prefixed tableaux, and solves both Abduction and Contraction in a uniform way. Recent tableaux methods for DLs could be easily extended to truth-prefixed tableaux. We also analyze the complexity of the problems for the DL named ALN, and show that the upper bound given by our methods meet the complexity lower bounds.

Keywords: Description Logics, Abduction, Tableaux, Belief Revision

Citation: Simona Colucci, Tommaso Di Noia, Eugenio Di Sciascio, Francesco M Donini, Marina Mongiello: A Uniform Tableaux-based Method for Abduction and Contraction in Description Logics. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.977-978.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).