Justification and debugging of answer set programs in ASP

ABSTRACT

The paper extends the concept of justification to the context of Answer Set Programming---a recent paradigm that builds on the foundations of logic programming, answer set semantics, and non-monotonic reasoning. A justification describes the support for the truth value of each atom in an answer set of a logic program, and it can be employed as a tool for reasoning and debugging of answer set programs. The paper describes the implementation of the notion of justification in the ASP system along with some examples of its applications.

REFERENCES

• 1: Chitta Baral, Knowledge Representation, Reasoning, and Declarative Problem Solving, Cambridge University Press, New York, NY, 2003
• 2: J. Boye et al. Declarative Diagnosis of Constraint Programs. AADEBUG, 1997.
• 3: Marco Comini , Giorgio Levi , Giuliana Vitiello, Abstract Debugging of Logic Program, Proceedings of the 4th International Workshops on Logic Programming Synthesis and Transformation - Meta-Programming in Logic, p.440-450, June 20-21, 1994
• 4: Pierre Deransart, Proof methods of declarative properties of definite programs, Theoretical Computer Science, v.118 n.2, p.99-166, Sept. 27, 1993 [doi>10.1016/0304-3975(93)90107-5]
• 5: W. Drabent. The Use of Assertions in Algorithmic Debugging. FGCS, 1988.
• 6: Mireille Ducassé , Ludovic Langevine, Automated Analysis of CLP(FD) Program Execution Traces, Proceedings of the 18th International Conference on Logic Programming, p.470-471, July 29-August 01, 2002
• 7: O. Elkhatib et al. A System for Reasoning about ASP in Prolog. PADL, Springer, 2004.
• 8: G. Ferrand, Error diagnosis in logic programming, an adaptation of E.Y. Shapiro's method, Journal of Logic Programming, v.4 n.3, p.177-198, Sept. 1987 [doi>10.1016/0743-1066(87)90001-X]
• 9: M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programs. JICSLP, MIT, 1988.
• 10: Hai-Feng Guo , C. R. Ramakrishnan , I. V. Ramakrishnan, Speculative Beats Conservative Justification, Proceedings of the 17th International Conference on Logic Programming, p.150-165, November 26-December 01, 2001
• 11: M. Hermenegildo et al. The CIAO Multi-Dialect Compiler and System. Parallelism and Implementation of Logic Programming, Nova Science, 1999.
• 12: Manuel V. Hermenegildo , Germán Puebla , Francisco Bueno , Pedro López-García, Integrated program debugging, verification, and optimization using abstract interpretation (and the Ciao system preprocessor), Science of Computer Programming, v.58 n.1-2, p.115-140, October 2005 [doi>10.1016/j.scico.2005.02.006]
• 13: L. Langevine et al. A Propagation Tracer for GNU-Prolog. ICLP, Springer Verlag, 2003.
• 14: J. W. Lloyd, Declarative error diagnosis, New Generation Computing, v.5 n.2, p.133-154, Oct. 1987 [doi>10.1007/BF03037396]
• 15: V.W. Marek and M. Truszczyński. Stable Models and an Alternative Logic Programming Paradigm. The Logic Programming Paradigm. Springer Verlag, 1999.
• 16: L. Naish et al. The NU-Prolog Debugging Environment. ICLP, pages 521--536, 1989.
• 17: Ilkka Niemelä, Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence, v.25 n.3-4, p.241-273, 1999 [doi>10.1023/A:1018930122475]
• 18: G. Pemmasani et al. Online Justification for Tabled Logic Programs. FLOPS, Springer Verlag, 2004.
• 19: Partha S. Roop , A. Sowmya , S. Ramesh, Forced simulation: A technique for automating component reuse in embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.602-628, October 2001 [doi>10.1145/502175.502185]
• 20: Abhik Roychoudhury , C. R. Ramakrishnan , I. V. Ramakrishnan, Justifying proofs using memo tables, Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.178-189, September 20-23, 2000, Montreal, Quebec, Canada [doi>10.1145/351268.351290]
• 21: Ehud Y. Shapiro, Algorithmic program diagnosis, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.299-308, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582185]
• 22: T. Syrjänen. Lparse User's Manual. http://www.tcs.hut.fi/Software/smodels/.
• 23: J.L. Yuh and N. Dershowitz. Debugging Logic Programs using Specifications. AADEBUG, 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Languages, Verification

Keywords:
justifications, logic programming, small answer set programming