Abduction in Well-Founded Semantics and Generalized Stable Models via Tabled Dual Programs

Title: Abduction in Well-Founded Semantics and Generalized Stable Models via Tabled Dual Programs

Research Question: How can we efficiently compute queries over abductive frameworks that are based on extended logic programs with integrity constraints, and whose notion of entailment rests on the well-founded semantics and its partial stable models?

Methodology: The authors propose a technique called Abdual for query processing. It involves a program transformation and tabled evaluation. The transformation removes default negative literals from the program and defines a dual set of rules for each objective literal. The resulting program is then evaluated using tabled logic programming. This approach allows for efficient computation of queries over negation, while preserving termination and complexity properties of extended programs.

Results: Abdual is shown to be sound and complete for evaluating queries to abductive frameworks whose entailment method is based on the well-founded semantics with explicit negation, or on answer sets. Furthermore, it is asymptotically as efficient as any known method for these classes of problems. Additionally, when abduction is not desired, Abdual operating on a dual program provides a novel tabling method for evaluating queries to ground extended programs.

Implications: The work has significant implications for the field of abductive logic programming and tabled logic programming. It offers a new method for efficiently computing queries over abductive frameworks, and provides a novel tabling method for evaluating queries to extended logic programs. This could lead to advancements in various applications such as diagnosis, planning, and belief revision.

Link to Article: https://arxiv.org/abs/0312057v1 Authors: arXiv ID: 0312057v1