ECAI 2004 Conference Paper

[full paper]

Abduction over unbounded domains via ASP

Piero A. Bonatti

It is known that abduction can be embedded into Answer Set programming (ASP). This enables sophisticated answer set solvers to be applied to various problems that can be expressed as abduction problems. However this approach does not scale to abduction over infinite domains, nor to unbounded individual abduction, due to well-known undecidability results. The approaches to open abduction usually rely on 3-valued semantics to overcome technical difficulties, but this 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, standard ASP engines can be adapted to compute the set of representative explanations.

Keywords: Answer set programming, Abduction, Open domains, Finitary programs

Citation: Piero A. Bonatti: Abduction over unbounded domains via ASP. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.288-292.