Verifying the Equivalence of Logic Programs in the Disjunctive Case | SpringerLink
Skip to main content
Springer Nature Link
Log in

Verifying the Equivalence of Logic Programs in the Disjunctive Case

  • Conference paper
Logic Programming and Nonmonotonic Reasoning (LPNMR 2004)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2923))

Abstract

In this paper, we address the problem of checking whether two disjunctive logic programs possess exactly the same stable models. An existing translation-based method [14], which was designed for weight constraint programs supported by the smodels system, is generalized to the disjunctive case. Moreover, we report on our preliminary experiments with an implementation of the method, a translator called dlpeq.

The research reported in this paper is partially funded by the Academy of Finland under the project “Applications of Rule-Based Constraint Programming” (#53695).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Balduccini, M., Gelfond, M., Watson, R., Nogueira, M.: The USA-advisor: A case study in answer set planning. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 439–442. Springer, Heidelberg (2001)

    Google Scholar 

  2. Eiter, T., Fink, M.: Uniform equivalence of logic programs under the stable model semantics. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 224–238. Springer, Heidelberg (2003) (to appear)

    Chapter  Google Scholar 

  3. Eiter, T., Gottlob, G.: On the computational cost of disjunctive logic programming: Propositional case. Annals of Math. and AI 15, 289–323 (1995)

    MATH  MathSciNet  Google Scholar 

  4. Ferraris, P., Lifschitz, V.: Weight constraints as nested expressions (2003) (unpublished draft), Available at http://www.cs.utexas.edu/users/vl/papers.html

  5. Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Proc. of the 5th International Conference on Logic Programming, Seattle, USA, August 1988, pp. 1070–1080. MIT Press, Cambridge (1988)

    Google Scholar 

  6. Gelfond, M., Lifschitz, V.: Logic programs with classical negation. In: Proc. of the 7th International Conference on Logic Programming, Jerusalem, Israel, June 1990, pp. 579–597. MIT Press, Cambridge (1990)

    Google Scholar 

  7. Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385 (1991)

    Article  Google Scholar 

  8. Gent, I., Walsh, T.: Beyond NP: the QSAT phase transition. In: Proc. of the 16th National Conference on Artificial Intelligence and the 11th Conference on Innovative Applications of Artificial Intelligence, Orlando, Florida, USA, July 1999, pp. 648–653. AAAI/MIT Press (1999)

    Google Scholar 

  9. Inoue, K., Sakama, C.: Negation as failure in the head. Journal of Logic Programming 35(1), 39–78 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Janhunen, T.: On the effect of default negation on the expressiveness of disjunctive rules. In: Logic Programming and Nonmonotonic Reasoning, Proc. of the 6th International Conference, Vienna, Austria, September 2001, pp. 93–106. Springer, Heidelberg (2001)

    Google Scholar 

  11. Janhunen, T.: LPEQ 1.13 – a tool for testing the equivalence of logic programs. Computer Program (2002), http://www.tcs.hut.fi/Software/lpeq/

  12. Janhunen, T.: GnT 2 – a tool for computing disjunctive stable models. Computer Program (2003), http://www.tcs.hut.fi/Software/gnt/

  13. Janhunen, T., Niemelä, I., Seipel, D., Simons, P., You, J.-H.: Unfolding partiality and disjunctions in stable model semantics. CoRR: cs.AI/0303009 (March 2003)

    Google Scholar 

  14. Janhunen, T., Oikarinen, E.: Testing the equivalence of logic programs under stable model semantics. In: Logics in Artificial Intelligence, Proc. of the 8th European Conference, Cosenza, Italy, September 2002, pp. 493–504. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  15. Leone, N., et al.: The DLV system for knowledge representation and reasoning. CoRR: cs.AI/0211004 (September 2003)

    Google Scholar 

  16. Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Transactions on Computational Logic 2, 526–541 (2001)

    Article  MathSciNet  Google Scholar 

  17. Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Annals of Math. and AI 25(3-4), 369–389 (1999)

    MATH  MathSciNet  Google Scholar 

  18. Lin, F.: Reducing strong equivalence of logic programs to entailment in classical propositional logic. In: Fensel, D., et al. (eds.) Principles of Knowledge Representation and Reasoning: Proc. of the 8th International Conference, Tolouse, France, April 2002, pp. 170–176. Morgan Kaufmann, San Francisco (2002)

    Google Scholar 

  19. Lloyd, J.W.: Foundations of Logic Programming. Springer, Berlin (1987)

    MATH  Google Scholar 

  20. Marek, W., Truszczyński, M.: Autoepistemic logic. Journal of the ACM 38, 588–619 (1991)

    Article  MATH  Google Scholar 

  21. Marek, W., Truszczyński, M.: Stable models and an alternative logic programming paradigm. In: The Logic Programming Paradigm: a 25-Year Perspective, pp. 375–398. Springer, Heidelberg (1999)

    Google Scholar 

  22. Niemelä, I.: Logic programs with stable model semantics as a constraint programming paradigm. Annals of Math. and AI 25(3-4), 241–273 (1999)

    MATH  Google Scholar 

  23. Oikarinen, E.: DLPEQ 1.9 – a tool for testing the equivalence of disjunctive logic programs. Computer Program (2003), http://www.tcs.hut.fi/Software/lpeq/

  24. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)

    MATH  Google Scholar 

  25. Pearce, D., Sarsakov, V., Schaub, T., Tompits, H., Woltran, S.: A polynomial translation of logic programs with nested expressions into disjunctive logic programs: Preliminary report. In: Proc. of the 18th International Conference on Logic Programming, Copenhagen, Denmark, July-August 2002, pp. 405–420. Springer, Heidelberg (2002)

    Google Scholar 

  26. Pearce, D., Tompits, H., Woltran, S.: Encodings for equilibirium logic and logic programs with nested expressions. In: Proc. of the 10th Portuguese Conference on Artificial Intelligence, Porto, Portugal, December 2001, pp. 306–320. Springer, Heidelberg (2001)

    Google Scholar 

  27. Przymusinski, T.: Extended stable semantics for normal and disjunctive logic programs. In: Proc. of the 7th International Conference on Logic Programming, pp. 459–477. MIT Press, Cambridge (1990)

    Google Scholar 

  28. Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics. Artificial Intelligence 138(1-2), 181–234 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  29. Turner, H.: Strong equivalence made easy: Nested expressions and weight constraints. Theory and Practice of Logic Programming 3(4-5), 609–622 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Laboratory for Theoretical Computer Science, Helsinki University of Technology, P.O. Box 5400, FIN-02015 HUT, Finland

    Emilia Oikarinen & Tomi Janhunen

Authors
  1. Emilia Oikarinen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomi Janhunen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Sciences, University of Texas at Austin, USA

    Vladimir Lifschitz

  2. Department of Information and Computer Science, Helsinki University of Technology TKK,  

    Ilkka Niemelä

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Oikarinen, E., Janhunen, T. (2003). Verifying the Equivalence of Logic Programs in the Disjunctive Case. In: Lifschitz, V., Niemelä, I. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2004. Lecture Notes in Computer Science(), vol 2923. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24609-1_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-24609-1_17

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20721-4

  • Online ISBN: 978-3-540-24609-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics