Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-16T09:23:46.322Z Has data issue: false hasContentIssue false
  • English
  • Français

Justifications for logic programs under answer set semantics

Published online by Cambridge University Press:  01 January 2009

ENRICO PONTELLI ,
TRAN CAO SON  and
OMAR ELKHATIB
ENRICO PONTELLI
Affiliation:
Department of Computer Science, New Mexico State University, Las Cruces, NM, USA (e-mail: [email protected], [email protected], [email protected])
TRAN CAO SON
Affiliation:
Department of Computer Science, New Mexico State University, Las Cruces, NM, USA (e-mail: [email protected], [email protected], [email protected])
OMAR ELKHATIB
Affiliation:
Department of Computer Science, New Mexico State University, Las Cruces, NM, USA (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper introduces the notion of offline justification for answer set programming (ASP). Justifications provide a graph-based explanation of the truth value of an atom with respect to a given answer set. The paper extends also this notion to provide justification of atoms during the computation of an answer set (on-line justification) and presents an integration of online justifications within the computation model of Smodels. Offline and online justifications provide useful tools to enhance understanding of ASP, and they offer a basic data structure to support methodologies and tools for debugging answer set programs. A preliminary implementation has been developed in – .

Keywords

answer set programmingjustificationoffline justificationonline justification
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 9 , Issue 1 , January 2009 , pp. 1 - 56
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anger, C., Gebser, M., Linke, T., Neumann, A. and Schaub, T. 2005. The nomore++ approach to answer set solving. In Logic for Programming, Artificial Intelligence, and Reasoning, 12th International Conference (LPAR), Sutcliffe, G. and Voronkov, A., Eds. Springer Verlag, Berlin Heidelberg, 95–109.Google Scholar
Apt, K. and Bol, R. 1994. Logic programming and negation: A survey. Journal of Logic Programming 19, 20, 9–71.CrossRefGoogle Scholar
Arora, T., Ramakrishnan, R., Roth, W., Seshadri, P. and Drivastava, D. 1993. Explaining program execution in deductive systems. In Deductive and Object-Oriented Databases, Third International Conference (DOOD), Ceri, S., Tanaka, K., and Tsur, S., Eds. Springer Verlag, Berlin Heidelberg, 101–119.CrossRefGoogle Scholar
Auguston, M. 2000. Assertion checker for the C programming language based on computations over event traces. In Proceedings of the Fourth International Workshop on Automated Debugging (AADEBUG), Ducasse, M., Ed. arXiv:cs/0010035, http://xxx.lanl.gov/abs/cs.SE/0010035.Google Scholar
Balduccini, M. 2007. CR-models: An inference engine for CR-Prolog. In Logic Programming and Nonmonotonic Reasoning, 9th International Conference (LPNMR), Baral, C., Brewka, G., and Schlipf, J. S., Eds. Springer Verlag, Berlin Heiderlberg, 18–30.CrossRefGoogle Scholar
Balduccini, M. and Gelfond, M. 2003. Diagnostic Reasoning with A-Prolog. Theory and Practice of Logic Programming 3, 4–5, 425–461.CrossRefGoogle Scholar
Balduccini, M., Gelfond, M. and Nogueira, M. 2006. Answer set based design of knowledge systems. Annals of Mathematics and Artificial Intelligence, 47, 1–2, 183–219.CrossRefGoogle Scholar
Baral, C. 2003. Knowledge Representation, Reasoning, and Declarative Problem Solving with Answer Sets. Cambridge University Press, Cambridge, MA.CrossRefGoogle Scholar
Brain, M. and de Vos, M. 2005. Debugging logic programs under the answer set semantics. In Answer Set Programming, Advances in Theory and Implementation, Proceedings of the 3rd International ASP Workshop, CEUR Workshop Proceedings, de Vos, M. and Provetti, A., Eds. 142 CEUR-WS.org, 142–152.Google Scholar
Brain, M., Gebser, M., Pührer, J., Schaub, T., Tompits, H. and Woltran, S. 2007a. Debugging ASP programs by means of ASP. In Proc. of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07), Baral, C., Brewka, G., and Schlipf, J., Eds. Lecture Notes in Artificial Intelligence, vol. 4483. Springer Verlag, Berlin Heidelberg, 31–43.CrossRefGoogle Scholar
Brain, M., Gebser, M., Pührer, J., Schaub, T., Tompits, H. and Woltran, S. 2007b. “That is illogical captain!”–-The debugging support tool spock for answer-set programs: System description. In Proc. of the Workshop on Software Engineering for Answer Set Programming (SEA'07), De Vos, M. and Schaub, T., Eds. 71–85.Google Scholar
Brass, S., Dix, J., Freitag, B. and Zukowski, U. 2001. Transformation-based bottom-up computation of the well-founded model. Theory and Practice of Logic Programming 1, 5, 497–538.CrossRefGoogle Scholar
Costantini, S. 2001. Comparing different graph representations of logic programs under the Answer Set semantics. In Answer Set Programming, Towards Efficient and Scalable Knowledge Representation and Reasoning, Proceedings of the First International ASP Workshop, AAAI Spring Symposium, Technical Report SS-01-01, Provetti, A. and Son, T. C., Eds. AAAI Press, Menlo Park, 21–26.Google Scholar
Costantini, S., D'Antona, O. M. and Provetti, A. 2002. On the equivalence and range of applicability of graph-based representations of logic programs. Information Processing Letters 84, 5, 241–249.CrossRefGoogle Scholar
Davis, M., Logemann, G. and Loveland, D. W. 1962. A machine program for theorem-proving. Communications of the ACM 5, 7, 394–397.CrossRefGoogle Scholar
Debray, S., Lopez-Garcia, P., Hermenegildo, M. and Lin, N. 1997. Lower bound cost estimation for logic programs. In International Logic Programming Symposium. MIT Press, Cambridge, MA, 291–305.Google Scholar
Delgrande, J., Schaub, T. and Tompits, H. 2003. A framework for compiling preferences in logic programs. Theory and Practice of Logic Programming 3, 2, 129–187.CrossRefGoogle Scholar
Deransart, P., Hermenegildo, M. V. and Maluszynski, J., Eds. 2000. Analysis and Visualization Tools for Constraint Programming, Constrain Debugging (DiSCiPl project). Lecture Notes in Computer Science, Vol. 1870. Springer Verlag, Berlin Heidelberg.CrossRefGoogle Scholar
Ducassé, M. 1999. Opium: An extendable trace analyzer for prolog. Journal of Logic Programming 39, 1–3, 177–223.CrossRefGoogle Scholar
Eiter, T., Leone, N., Mateis, C., Pfeifer, G. and Scarcello, F. 1998. The KR system DLV: Progress report, comparisons, and benchmarks. In International Conference on Principles of Knowledge Representation and Reasoning, Cohn, A. C., Shubert, L. K., and Shapiro, S. C., Eds. Morgan Kaufmann Publishers, San Francisco, 406–417.Google Scholar
Elkhatib, O., Pontelli, E. and Son, T. C. 2005. Justification and debugging of answer set programs in ASP. In Proc. of the Sixth International Workshop on Automated Debugging, AADEBUG 2005, Jeffery, C., Choi, J.-D., and Lencevicius, R., Eds. ACM Press, New York, 49–58.Google Scholar
Elkhatib, O., Pontelli, E. and Son, T. 2004. ASP-Prolog: A system for reasoning about answer set programs in Prolog. In Proc. of the Sixth International Symposium on Practical Aspects of Declarative Languages (PADL-2004). Springer Verlag, Berlin Heidelberg, 148–162.CrossRefGoogle Scholar
Erdem, E., Lifschitz, V. and Ringe, D. 2006. Temporal phylogenetic networks and logic programming. Theory and Practice of Logic Programming 6, 5, 539–558.CrossRefGoogle Scholar
Fages, F. 1994. Consistency of Clark's completion and existence of stable models. Methods of Logic in Computer Science 1, 51–60.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. clasp: A conflict-driven answer set solver. In Proc. of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07), Baral, C., Brewka, G., and Schlipf, J., Eds. Lecture Notes in Artificial Intelligence, vol. 4483. Springer Verlag, Berlin Heidelberg, 260–265.CrossRefGoogle Scholar
Gebser, M., Schaub, T. and Thiele, S. 2007. Gringo: A new grounder for answer set programming. In Proc. of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07), Baral, C., Brewka, G., and Schlipf, J., Eds. Lecture Notes in Artificial Intelligence, vol. 4483. Springer Verlag, Berlin Heidelberg, 266–271.CrossRefGoogle Scholar
Gelfond, M. and Leone, N. 2002. Logic programming and knowledge representation – the A-Prolog perspective. Artificial Intelligence 138, 1–2, 3–38.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proceedings of the Fifth International Conf. and Symp., Kowalski, R. and Bowen, K., Eds. MIT Press, Cambridge, MA, 1070–1080.Google Scholar
Giunchiglia, E., Lierler, Y. and Maratea, M. 2004. SAT-based answer set programming. In Proc. of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence. AAAI Press/MIT Press, Cambridge, MA, 61–66.Google Scholar
Giunchiglia, E. and Maratea, M. 2005. On the relation between answer set and SAT procedures (or, between Cmodels and Smodels). In Logic Programming, 21st International Conference, ICLP 2005, Gabbrielli, M. and Gupta, G., Eds. Lecture Notes in Computer Science, vol. 3668. Springer Verlag, Berlin Heidelberg, 37–51.Google Scholar
Gras, D. C. and Hermenegildo, M. V. 2000. A new module system for prolog. In Computational Logic–-CL 2000, First International Conference, Lloyd, J. W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Palamidessi, C., Pereira, L. M., Sagiv, Y., and Stuckey, P. J., Eds. Lecture Notes in Computer Science, vol. 1861. Springer Verlag, Berlin Heidelberg, 131–148.Google Scholar
Guo, H., Ramakrishnan, C. and Ramakrishnan, I. 2001. Speculative beats conservative justification. In International Conference on Logic Programming. Springer Verlag, Berlin Heidelberg, 150–165.CrossRefGoogle Scholar
Heljanko, K. and Niemelä, I. 2003. Bounded LTL model checking with stable models. Theory and Practice of Logic Programming 3 4–5, 519–550.CrossRefGoogle Scholar
Konczak, K., Linke, T. and Schaub, T. 2006. Graphs and colorings for answer set programming. Theory and Practice of Logic Programming 6, 1–2, 61–106.CrossRefGoogle Scholar
Lifschitz, V. 1999. Answer set planning. In International Conference on Logic Programming, MIT Press, Cambridge, MA, 23–37.Google Scholar
Lifschitz, V. 2002. Answer set programming and plan generation. Artificial Intelligence 138, 1–2, 39–54.CrossRefGoogle Scholar
Lin, F. and Zhao, Y. 2002. ASSAT: Computing answer sets of a logic program by SAT solvers. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, AAAI Press, Menlo Park, 112–117.Google Scholar
Lloyd, J. 1987. Foundations of Logic Programming, 2nd ed. Springer Verlag, Berlin Heidelberg.CrossRefGoogle Scholar
Mallet, S. and Ducassé, M. 1999. Generating deductive database explanations. In International Conference on Logic Programming, MIT Press, Cambridge, MA, 154–168.Google Scholar
Marek, V. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-year Perspective, Springer Verlag, Berlin Heidelberg, 375–398.CrossRefGoogle Scholar
Mera, E., Lopez-Garcia, P., Puebla, G., Carro, M. and Hermenegildo, M. 2006. Using combined static analysis and profiling for logic program execution time estimation. In International Conference on Logic Programming. Springer Verlag, Berlin Heidelberg, 431–432.CrossRefGoogle Scholar
Niemelä, I. 1999. Logic programming with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273.CrossRefGoogle Scholar
Niemela, I. and Simons, P. 1997. Smodels – an implementation of the stable model and well-founded semantics for normal logic programs. In Logic Programming and Nonmonotonic Reasoning, Fourth International Conference (LPNMR), Dix, J., Furbach, U., and Nerode, A., Eds. Springer Verlag, Berlin Heidelberg, 420–429.CrossRefGoogle Scholar
Pemmasani, G., Guo, H.-F., Dong, Y., Ramakrishnan, C. R. and Ramakrishnan, I. V. 2004. Online justification for tabled logic programs. In Functional and Logic Programming, 7th International Symposium, FLOPS 2004, Kameyama, Y. and Stuckey, P. J., Eds. Lecture Notes in Computer Science, vol. 2998. Springer Verlag, Berlin Heidelberg, 24–38.Google Scholar
Perri, S., Ricca, F., Terracina, G., Cianni, D. and Veltri, P. 2007. An integrated graphic tool for developing and testing DLV programs. In Proc. of the 1st SEA Workshop, LPNMR'07, 86–100.Google Scholar
Pineda, A. and Hermenegildo, M. 1999. O'CIAO An Object Oriented Programming model using CIAO Prolog. Technical Report CLIP 5/99.0, Facultad de Informatica, Universidad Politecnica de Madrid, Spain.Google Scholar
Puebla, G., Bueno, F. and Hermenegildo, M. V. 1998. A framework for assertion-based debugging in constraint logic programming. In Principles and Practice of Constraint Programming–-CP98, 4th International Conference, Maher, M. J. and Puget, J.-F., Eds. Lecture Notes in Computer Science, vol. 1520. Springer Verlag, Berlin Heidelberg, 472.CrossRefGoogle Scholar
Roychoudhury, A., Ramakrishnan, C. R. and Ramakrishnan, I. V. 2000. Justifying proofs using memo tables. In Second International Conference on Principles and Practice of Declarative Programming, Gabbrielli, M. and Pfenning, F., Eds. ACM Press, New York, 179–189.Google Scholar
Saha, D. and Ramakrishnan, C. R. 2005. Symbolic support graph: A space efficient data structure for incremental tabled evaluation. In Logic Programming, 21st International Conference, ICLP 2005, Gabbrielli, M. and Gupta, G., Eds. Lecture Notes in Computer Science, vol. 3668. Springer Verlag, Berling Heidelberg, 235–249.Google Scholar
Shapiro, E. Y. 1982. Algorithmic program diagnosis. In Proceedings of the Ninth Annual ACM Symposium on Principles of Programming Languages, ACM Press, New York, 299–308.Google Scholar
Simons, P., Niemelä, N. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1–2, 181–234.CrossRefGoogle Scholar
Specht, G. 1993. Generating Explanation Trees even for Negations in Deductive DataBase Systems. In Proceedings of the Fifth Workshop on Logic Programming Environments (LPE), IRISA Technical Report, Rennes Cedex, Ducasse, M., Le Charlier, B., Lin, Y-J., and Yalcinalp, L. U., Eds. 8–13.Google Scholar
Syrjänen, T. 2006. Debugging inconsistent answer set programs. In Proceedings of the 11th International Workshop on Non-Monotonic Reasoning, Technical Report, Technische Universitaet Clausthal, Dix, J. and Hunter, A., Eds. http://www.in.tu-clausthal.de/abteilungen/cig/cigroot/activities/nmr-06, 77–84.Google Scholar
Van Emden, M., and Kowalski, R. 1976. The semantics of predicate logic as a programming language. Journal of the ACM. 23, 4, 733–742.CrossRefGoogle Scholar
Van Gelder, A., Ross, K. and Schlipf, J. 1991. The well-founded semantics for general logic programs. Journal of ACM 38, 3, 620–650.CrossRefGoogle Scholar
Vaupel, R., Pontelli, E. and Gupta, G. 1997. Visualization of and/or-parallel execution of logic programs. In Logic Programming, Proceedings of the Fourteenth International Conference (ICLP), Naish, L., Ed. MIT Press, Cambridge, MA, 271–285.Google Scholar