Abstract:
Justification is the process of constructing evidence, in terms of proof, for the truth or falsity of an answer. In earlier works we presented algorithms for justifying tabled logic programs, based on post-processing memo-tables created during evaluation. In this paper we introduce online justification to address two efficiency drawbacks of post-processing based justification, namely cycle checking and meta-interpretation of the memo tables with respect to the clauses of the program.
Online justification is based on program transformation. Specifically, every predicate in the original program corresponds to two predicates in the transformed program, viz., an evidence predicate and a dual predicate. Whenever a query in the original program has an answer, the corresponding query to its evidence predicate generates the answer and its evidence simultaneously. Whenever a query in the original program fails, the corresponding query to its dual predicate generates an evidence for the failure. We provide experimental evidence to show that online justification outperforms previous techniques in both efficiency and scalability. Moreover, online justification separates evidence generation from exploration thereby providing flexibility in exploring the evidence either declaratively or procedurally.
This is a short paper, which has been subsequently expanded and presented at FLOPS 2004
Bibtex Entry:
@inproceedings{PGDRR:ICLP03, author = {Giridhar Pemmasani and Haifeng Guo and Yifei Dong and C. R. Ramakrishnan and I. V. Ramakrishnan}, title = {Online Justification for Tabled Logic Programs}, booktitle = {International Conference on Logic Programming ({ICLP})}, address = {Mumbai, India}, month = {December}, series = {Lecture Notes in Computer Science}, volume = {2916}, publisher = {Springer}, pages = {500--501}, year = {2003} }
C. R. Ramakrishnan
(cram@cs.sunysb.edu)