Abduction is one of the most important forms of reasoning; it has been successfully applied to several practical problems, such as diagnosis. In this article we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) is often known before the rest of the problem. In this article, we show some complexity results about abduction when compilation is allowed.

Compilability of Propositional Abduction / Liberatore, Paolo; Schaerf, Marco. - In: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC. - ISSN 1529-3785. - 8(1):(2007), pp. 65-83. [10.1145/1182613.1182615]

Compilability of Propositional Abduction

LIBERATORE, Paolo;SCHAERF, Marco
2007

Abstract

Abduction is one of the most important forms of reasoning; it has been successfully applied to several practical problems, such as diagnosis. In this article we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) is often known before the rest of the problem. In this article, we show some complexity results about abduction when compilation is allowed.
01 Pubblicazione su rivista::01a Articolo in rivista
Compilability of Propositional Abduction / Liberatore, Paolo; Schaerf, Marco. - In: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC. - ISSN 1529-3785. - 8(1):(2007), pp. 65-83. [10.1145/1182613.1182615]
File allegati a questo prodotto
File Dimensione Formato  
VE_2007_11573-236024.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 147.95 kB
Formato Adobe PDF
147.95 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/236024
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 1
social impact