Propositional Abduction with Implicit Hitting Sets
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Backdoors to Abduction
Abductive reasoning (or Abduction, for short) is among the most fundamental AI reasoning methods, with a broad range of applications, including fault diagnosis, belief revision, and automated planning. Unfortunately, Abd…
Fault DiagnosisComplexity of Faceted Explanations in Propositional Abduction
Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artificial intelligence and database updates.…
Propositional Abduction via Only-Knowing: A Non-Monotonic Approach
The paper introduces a basic logic of knowledge and abduction by extending Levesque logic of only-knowing with an abduction modal operator defined via the combination of basic epistemic concepts. The upshot is an alterna…
Representative Sets in Propositional Abduction
The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined qu…
Morphologic for knowledge dynamics: revision, fusion, abduction
Several tasks in artificial intelligence require to be able to find models about knowledge dynamics. They include belief revision, fusion and belief merging, and abduction. In this paper we exploit the algebraic framewor…