Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-24T05:56:53.242Z Has data issue: false hasContentIssue false
  • English
  • Français

Automated Verification of Weak Equivalence within the smodels System*

Published online by Cambridge University Press:  01 November 2007

TOMI JANHUNEN  and
EMILIA OIKARINEN
TOMI JANHUNEN
Affiliation:
Helsinki University of Technology, Department of Computer Science and Engineering, Laboratory for Theoretical Computer Science, P.O. Box 5400, FI-02015 TKK, Finland (e-mail: [email protected], [email protected])
EMILIA OIKARINEN
Affiliation:
Helsinki University of Technology, Department of Computer Science and Engineering, Laboratory for Theoretical Computer Science, P.O. Box 5400, FI-02015 TKK, Finland (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In answer set programming (ASP), a problem at hand is solved by (i) writing a logic program whose answer sets correspond to the solutions of the problem, and by (ii) computing the answer sets of the program using an answer set solver as a search engine. Typically, a programmer creates a series of gradually improving logic programs for a particular problem when optimizing program length and execution time on a particular solver. This leads the programmer to a meta-level problem of ensuring that the programs are equivalent, i.e., they give rise to the same answer sets. To ease answer set programming at methodological level, we propose a translation-based method for verifying the equivalence of logic programs. The basic idea is to translate logic programs P and Q under consideration into a single logic program EQT(P,Q) whose answer sets (if such exist) yield counter-examples to the equivalence of P and Q. The method is developed here in a slightly more general setting by taking the visibility of atoms properly into account when comparing answer sets. The translation-based approach presented in the paper has been implemented as a translator called lpeq that enables the verification of weak equivalence within the smodels system using the same search engine as for the search of models. Our experiments with lpeq and smodels suggest that establishing the equivalence of logic programs in this way is in certain cases much faster than naive cross-checking of answer sets.

Keywords

Answer set programmingweak equivalenceprogramming methodologyprogram optimization
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 7 , Issue 6 , November 2007 , pp. 697 - 744
Copyright
Copyright © Cambridge University Press 2007

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++ system. In Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Springer-Verlag, pp. 422–426. LNAI 3662.CrossRefGoogle Scholar
Apt, K., Blair, H. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann, pp. 89–148.CrossRefGoogle Scholar
Balduccini, M., Barry, M., Gelfond, M., Nogueira, M. and Watson, R. 2001. An A-Prolog decision support system for the space shuttle. In Proceedings of the Third International Symposium on Practical Aspects of Declarative Languages. Springer-Verlag, pp. 169–183.Google Scholar
Cholewinski, P. and Truszczyński, M. 1999. Extremal problems in logic programming and stable model computation. Journal of Logic Programming 38, 2, 219–242.CrossRefGoogle Scholar
Dovier, A., Formisano, A. and Pontelli, E. 2005. A comparison of CLP(FD) and ASP solutions to NP-complete problems. In Proceedings of Convegno Italiano di Logica Computazionale. Italian Association for Logic Programming (GULP), Rome, Italy. Available at http://www.disp.uniroma2.it/CILC2005/.CrossRefGoogle Scholar
Dowling, W. and Gallier, J. 1984. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming 3, 267–284.CrossRefGoogle Scholar
Eiter, T., Fink, M., Tompits, H. and Woltran, S. 2004. Simplifying logic programs under uniform and strong equivalence. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning, Lifschitz, V. and Niemelä, I., Eds. Springer-Verlag, pp. 87–99. LNAI 2923.Google Scholar
Eiter, T., Tompits, H. and Woltran, S. 2005. On solution correspondences in answer-set programming. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI'05. Professional Book Center, Edinburgh, Scotland, UK, pp. 97–102.Google Scholar
Eiter, T. and Wang, K. 2006. Forgetting and conflict resolving in disjunctive logic programming. In Proceedings of the 11th International Workshop on Nonmonotonic Reasoning, Dix, J. and Hunter, A., Eds. University of Clausthal, Department of Informatics, Technical Report, IfI-06-04, Lake District, UK, pp. 85–91. Available at http://www.in.tu-clausthal.de/forschung/technical-reports/.Google Scholar
Gelfond, M. and Leone, N. 2002. Logic programming and knowledge representation – the A-Prolog perspective. Artificial Intelligence 138, 3–38.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference on Logic Programming. MIT Press, pp. 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1990. Logic programs with classical negation. In Proceedings of the 7th International Conference on Logic Programming. The MIT Press, pp. 579–597.Google Scholar
Gressmann, J., Janhunen, T., Mercer, R.Schaub, T., Tichy, R. and Thiele, S. 2005. Platypus: A platform for distributed answer set solving. In Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Springer-Verlag, pp. 227–239. LNAI 3662.CrossRefGoogle Scholar
Janhunen, T. 2003. Translatability and intranslatability results for certain classes of logic programs. Series A: Research report 82, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland. November. Available at http://www.tcs.hut.fi/Publications/series-a.shtml.Google Scholar
Janhunen, T. 2004. Representing normal programs with clauses. In Proceedings of the 16th European Conference on Artificial Intelligence, M'ntaras, R. L. de and Saitta, L., Eds. IOS Press, pp. 358–362.Google Scholar
Janhunen, T. 2006. Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 1–2 (June), 35–86.CrossRefGoogle Scholar
Janhunen, T., Niemelä, I., Simons, P. and You, J.-H. 2000. Unfolding partiality and disjunctions in stable model semantics. In Principles of Knowledge Representation and Reasoning: Proceedings of the 7th International Conference, Cohn, A., Giunchiglia, F., and Selman, B., Eds. Morgan, Kaufmann, Breckenridge, Colorado, 411–419.Google Scholar
Janhunen, T., Niemelä, I., Seipel, D., Simons, P. and You, J.-H. 2006. Unfolding partiality and disjunctions in stable model semantics. ACM Transactions on Computational Logic 7, 1, 1–37.CrossRefGoogle Scholar
Janhunen, T. and Oikarinen, E. 2002. Testing the equivalence of logic programs under stable model semantics. In Logics in Artificial Intelligence, Proceedings of the 8th European Conference, Flesca, S. et al. ., Eds. Springer-Verlag, pp. 493–504. LNAI 2424.Google Scholar
Janhunen, T. and Oikarinen, E. 2004. lpeq and dlpeq – translators for automated equivalence testing of logic programs. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning, Lifschitz, V. and Niemelä, I., Eds. Springer-Verlag, pp. 336–340. LNAI 2923.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic. 7, 3, 499–562.CrossRefGoogle Scholar
Lierler, Y. and Maratea, M. 2004. Cmodels-2: Sat-based answer set solver enhanced to non-tight programs. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning. Springer-Verlag, pp. 346–350. LNAI 2923.Google Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic 2, 526–541.CrossRefGoogle Scholar
Lin, F. 2002. Reducing strong equivalence of logic programs to entailment in classical propositional logic. In Principles of Knowledge Representation and Reasoning: Proceedings of the 8th International Conference, Fensel, D., Giunchiglia, F., McGuinness, D., and Williams, M.-A., Eds. Morgan Kaufmann, pp. 170–176.Google Scholar
Lin, F. and Zhao, Y. 2002. ASSAT: Computing answer sets of a logic program by SAT solvers. In Proceedings of the 18th National Conference on Artificial Intelligence. AAAI, AAAI Press, pp. 112–117.Google Scholar
Liu, L. and Truszczyński, M. 2005. Pbmodels software to compute stable models by pseudoboolean solvers. In Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Springer-Verlag, pp. 410–415. LNAI 3662.CrossRefGoogle Scholar
Lloyd, J. 1987. Foundations of Logic Programming. Springer-Verlag, Berlin.CrossRefGoogle Scholar
Marek, W. and Truszczy'nski, M. 1991. Autoepistemic logic. Journal of the ACM 38, 588–619.CrossRefGoogle Scholar
Marek, W. and Truszczy'nski, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: a 25-Year Perspective. Springer-Verlag, Berlin, 375–398.CrossRefGoogle Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273.CrossRefGoogle Scholar
Oikarinen, E. and Janhunen, T. 2004. Verifying the equivalence of logic programs in the disjunctive case. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning, Lifschitz, V. and Niemelä, I., Eds. Springer-Verlag, pp. 180–193. LNAI 2923.Google Scholar
Oikarinen, E. and Janhunen, T. 2006. Modular equivalence for normal logic programs. In Proceedings of the 17th European Conference on Artificial Intelligence. Riva del Garda, Italy, pp. 412–416.Google Scholar
Pearce, D., Tompits, H. and Woltran, S. 2001. Encodings for equilibirium logic and logic programs with nested expressions. In Proceedings of the 10th Portuguese Conference on Artificial Intelligence, Brazdil, P. and Jorge, A., Eds. Springer-Verlag, pp. 306–320. LNAI 2258.Google Scholar
Roth, D. 1996. On the hardness of approximate reasoning. Artificial Intelligence 82, 273–302.CrossRefGoogle Scholar
Simons, P. 1999. Extending the stable model semantics with more expressive rules. In Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning. Springer-Verlag, pp. 305–316. LNAI 1730.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1–2, 181–234.CrossRefGoogle Scholar
Soininen, T., Niemelä, I., Tiihonen, J. and Sulonen, R. 2001. Representing configuration knowledge with weight constraint rules. In Proceedings of the AAAI Spring 2001 Symposium on Answer Set Programming. AAAI Press, pp. 195–201.Google Scholar
Syrjänen, T. 2001. Lparse 1.0 user's manual. Available at http://www.tcs.hut.fi/Software/smodels.Google Scholar
Syrjänen, T. 2004. Cardinality constraint programs. In Logics in Artificial Intelligence: 9th European Conference, Alferes, J. and Leite, J., Eds. Springer-Verlag, pp. 187–200. LNAI 3229.CrossRefGoogle Scholar
Syrjänen, T. and Niemelä, I. 2001. The Smodels system. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, Eiter, T., Faber, W., and Truszczyński, M., Eds. Springer-Verlag, pp. 434–438. LNAI 2173.Google Scholar
Turner, H. 2003. Strong equivalence made easy: Nested expressions and weight constraints. Theory and Practice of Logic Programming 3, 4–5, 609–622.CrossRefGoogle Scholar