Tabled Abduction in Logic Programs.
Ari Saptawijaya, Luı́s Moniz Pereira · 2013
Abstract Abduction has been on the back burner in logic programming, as abduction can be too difficult to implement, and costly to perform, in particular if abductive solutions are not tabled for reuse. On the other hand, current Prolog systems, with their tabling mechanisms, are mature enough to facilitate the specific introduction of tabling abductive solutions (tabled abduction) into them. We conceptualize tabled abduction for abductive normal logic programs, permitting abductive solutions to be reused, from one abductive context to another. The approach relies on a program transformation into tabled logic programs that makes use of the dual transformation, and enables efficiently handling the problem of abduction under negative goals, by introducing dual positive counterparts for them. Tabled abduction is realized in Tabdual, a system implemented in XSB Prolog, where the dual transformation is refined to permit executing programs with variables and non-ground queries, and to allow performing dualization by-need only. Furthermore, we foster pragmatic approaches in Tabdual to cater to all varieties of loops in normal logic programs, now complicated by abduction. Tabdual has been evaluated in practice (with applications in declarative debugging and decision making) by examining its five variants, according to various evaluation objectives. Tabdual’s correctness and complexity are also referred, we identify its features that could migrate to the engine level, in Logic Programming systems wanting to encompass tabled abduction, and we summarize related work.