Well-founded abduction via tabled dual programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Downloads (Pure)

Abstract

Abductive Logic Programming offers a formalism to declaratively express and solve problems in areas such as diagnosis, planning, belief revision and hypothetical reasoning. Tabled Logic Programming offers a computational mechanism that provides a level of declarativity above that of Prolog, and which has supported successful applications in fields such as parsing, program analysis, and model checking, In this paper we show how to we tabled logic programming to evaluate queries to abductive frameworks with integrity constraints when these frameworks contain both default and explicit negation. Our approach consists of a transformation and an evaluation method. The transformation adjoins to each rule R of a finite ground program a new rule that is true if and only ii R is false. We call the resulting program a dual program. The evaluation method, ABDUAL, then operates on the dual program. ABDUAL is sound and complete for evaluating queries to abductive frameworks whose entailment method is based on either the well-founded semantics with explicit negation, or answer sets. Further, ABDUAL is asymptotically as efficient as any known method for either class of problems. In, addition, when abduction is not desired, ABDUAL operating on a dual program provides a novel tabling method for evaluating queries to ground extended programs whose complexity and termination properties are similar to those of the best tabling methods for the well-founded semantics. A publically available mete-interpreter has been developed for ABDUAL using the XSB system.
Original languageEnglish
Title of host publicationMIT Press
Pages426-440
Number of pages15
Publication statusPublished - 1 Jan 1999
EventInternational Conference on Logic Programming and Nonmonotonic Reasoning -
Duration: 1 Jan 1999 → …

Conference

ConferenceInternational Conference on Logic Programming and Nonmonotonic Reasoning
Period1/01/99 → …

Keywords

  • GENERAL LOGIC PROGRAMS
  • SEMANTICS

Fingerprint Dive into the research topics of 'Well-founded abduction via tabled dual programs'. Together they form a unique fingerprint.

  • Cite this