When looking for a propositional abductive explanation of a given set of manifestations, an ordering between possible solutions is often assumed. While the complexity of computing optimal solutions is already known, in this paper we consider second-best solutions with respect to different orderings, and different definitions of what a second-best solution is: an optimal solution not already found, or a solution that is optimal among the ones not previously found. © 2015 Elsevier Inc. Allrightsreserved.
On the complexity of second-best abductive explanations / Liberatore, Paolo; Schaerf, Marco. - In: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING. - ISSN 0888-613X. - STAMPA. - 63:(2015), pp. 22-31. [10.1016/j.ijar.2015.05.009]
On the complexity of second-best abductive explanations
LIBERATORE, Paolo
;SCHAERF, Marco
2015
Abstract
When looking for a propositional abductive explanation of a given set of manifestations, an ordering between possible solutions is often assumed. While the complexity of computing optimal solutions is already known, in this paper we consider second-best solutions with respect to different orderings, and different definitions of what a second-best solution is: an optimal solution not already found, or a solution that is optimal among the ones not previously found. © 2015 Elsevier Inc. Allrightsreserved.File | Dimensione | Formato | |
---|---|---|---|
Liberatore_On-the-complexity_Preprint_2015.pdf
accesso aperto
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Creative commons
Dimensione
310.18 kB
Formato
Adobe PDF
|
310.18 kB | Adobe PDF | |
Liberatore_On-the-complexity_2015.pdf
solo gestori archivio
Note: Versione Editore
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
368.28 kB
Formato
Adobe PDF
|
368.28 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.