Abduction over unbounded domains via ASP
Piero A. Bonatti · European Conference on Artificial Intelligence · 2004
It is known that abduction can be embedded into Answer Set programming (ASP). This enables sophisticated answer set solvers to be applied to abduction problems. However this approach does not scale to abduction over infinite domains, nor to unbounded abduction of individual existence, due to well-known un-decidability results. The approaches to open abduction usually rely on 3-valued semantics to overcome technical difficulties, but this approach changes the underlying semantics and prevents the application of ASP solvers. In this paper we apply the theory of finitary programs to prove that for an expressive and very interesting class of domain theories, ASP-based abduction with unbounded domains can effectively be computed. We also prove that each observable has a finite set of finite explanations representative of all the observable's infinitely many explanations. Moreover, the set of representative explanations can be computed with standard ASP engines.