Propositional abduction with implicit hitting sets

Alexey Ignatiev, Antonio Morgado, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)

Abstract

Logic-based abduction finds important applications in artificial intelligence and related areas. One application example is in finding explanations for observed phenomena. Propositional abduction is a restriction of abduction to the propositional domain, and complexity-wise is in the second level of the polynomial hierarchy. Recent work has shown that exploiting implicit hitting sets and propositional satisfiability (SAT) solvers provides an efficient approach for propositional abduction. This paper investigates this earlier work and proposes a number of algorithmic improvements. These improvements are shown to yield exponential reductions in the number of SAT solver calls. More importantly, the experimental results show significant performance improvements compared to the the best approaches for propositional abduction.

Original languageEnglish
Title of host publicationECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August–2 September 2016, The Hague, The Netherlands
Subtitle of host publicationIncluding - Prestigious Applications of Artificial Intelligence (PAIS 2016), Proceedings
EditorsGal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hullermeier, Virginia Dignum, Frank Dignum, Frank van Harmelen
Place of PublicationAmsterdam Netherlands
PublisherIOS Press
Pages1327-1335
Number of pages9
ISBN (Electronic)9781614996712
ISBN (Print)9781614996712
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventEuropean Conference on Artificial Intelligence 2016 - The Hague, Netherlands
Duration: 29 Aug 20162 Sep 2016
Conference number: 22nd
http://www.ecai2016.org/

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume285
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314

Conference

ConferenceEuropean Conference on Artificial Intelligence 2016
Abbreviated titleECAI 2016
CountryNetherlands
CityThe Hague
Period29/08/162/09/16
Internet address

Cite this

Ignatiev, A., Morgado, A., & Marques-Silva, J. (2016). Propositional abduction with implicit hitting sets. In G. A. Kaminka, M. Fox, P. Bouquet, E. Hullermeier, V. Dignum, F. Dignum, & F. van Harmelen (Eds.), ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August–2 September 2016, The Hague, The Netherlands: Including - Prestigious Applications of Artificial Intelligence (PAIS 2016), Proceedings (pp. 1327-1335). (Frontiers in Artificial Intelligence and Applications; Vol. 285). IOS Press. https://doi.org/10.3233/978-1-61499-672-9-1327