Non-monotonic reasoning: from complexity to algorithms - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1996

Non-monotonic reasoning: from complexity to algorithms

Résumé

The purpose of this paper is to outline various results regarding the computational complexity and the algorithms of nonmonotonic entailment in different coherence-based approaches. Starting from a (non necessarily consistent) belief base E and a pre-order on E, we first remind different mechanisms for selecting preferred consistent subsets. Then we present different entailment principles in order to manage these multiple subsets. The crossing point of each generation mechanism m and each entailment principle p defines an entailment relation which we study from the computational complexity point of view. The results are not very encouraging since the complexity of all these nonmonotonic entailment relations is, in most restricted languages, larger than the complexity of monotonic entailment. Therefore, we decided to extend Binary Decision Diagrams techniques, which are well suited to the task of solving NP-hard logicbased problems. Both theoretical and experimental results are described along this line in the last sections.
Fichier principal
Vignette du fichier
1996_Schiex_Rapport.pdf (447.04 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02842327 , version 1 (03-09-2020)

Identifiants

  • HAL Id : hal-02842327 , version 1
  • PRODINRA : 135883

Citer

Claudette Cayrol, Marie-Christine Lagasquie-Schiex, Thomas Schiex. Non-monotonic reasoning: from complexity to algorithms. [Research Report] Rapport IRIT--96.07R, IRIT : Institut de recherche en informatique de Toulouse; Toulouse 3 Paul Sabatier. 1996. ⟨hal-02842327⟩
51 Consultations
21 Téléchargements

Partager

Gmail Facebook X LinkedIn More