Skip to main content
Springer Nature Link
Log in

Inductive Equivalence of Logic Programs

  • Conference paper
Inductive Logic Programming (ILP 2005)

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

Included in the following conference series:

  • 579 Accesses

Abstract

This paper studies equivalence issues in inductive logic programming. A background theory B 1 is inductively equivalent to another background theory B 2 if B 1 and B 2 induce the same hypotheses for any given set of examples. Inductive equivalence is useful to compare inductive capabilities among agents having different background theories. Moreover, it provides conditions for optimizing background theories through appropriate program transformations. In this paper, we consider three different classes of background theories: clausal theories, Horn logic programs, and nonmonotonic extended logic programs. We show that logical equivalence is the necessary and sufficient condition for inductive equivalence in clausal theories and Horn logic programs. In nonmonotonic extended logic programs, on the other hand, strong equivalence is necessary and sufficient for inductive equivalence in general. Interestingly, however, we observe that several existing induction algorithms require weaker conditions of equivalence under restricted problem settings. We also discuss connection to equivalence in abductive logic and conclude that the notion of strong equivalence is useful to characterize equivalence of non-deductive reasoning.

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. Baral, C., Gelfond, M.: Logic programming and knowledge representation. Journal of Logic Programming 19/20, 73–148 (1994)

    Article  MathSciNet  Google Scholar 

  2. De Raedt, L.: Logical settings for concept-learning. Artificial Intelligence 95, 187–201 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  3. De Raedt, L., Dehaspe, L.: Clausal discovery. Machine Learning 26, 99–146 (1997)

    Article  MATH  Google Scholar 

  4. Denecker, M., Kakas, A.: Abductive logic programming. In: Kakas, A.C., Sadri, F. (eds.) Computational Logic: Logic Programming and Beyond. LNCS (LNAI), vol. 2407, pp. 402–436. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  5. 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)

    Chapter  Google Scholar 

  6. Flach, P.A., Kakas, A.C. (eds.): Abduction and Induction — Essays on their Relation and Integration. Kluwer Academic, Dordrecht (2000)

    MATH  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  9. Inoue, K.: Induction as consequent finding. Machine Learning 55, 109–135 (2004)

    Article  MATH  Google Scholar 

  10. Inoue, K., Sakama, C.: Equivalence of logic programs under updates. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 174–186. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  11. Inoue, K., Sakama, C.: Equivalence in abductive logic. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (2005) (to appear)

    Google Scholar 

  12. Janhunen, T., Oikarinen, E.: LPEQ and DLPEQ – translators for automated equivalence testing of logic programs. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS (LNAI), vol. 2923, pp. 336–340. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. Lin, F.: Reducing strong equivalence of logic programs to entailment in classical propositional logic. In: Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning, pp. 170–176. Morgan Kaufmann, San Francisco (2002)

    Google Scholar 

  15. Maher, M.J.: Equivalence of logic programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 627–658. Morgan Kaufmann, San Francisco (1988)

    Google Scholar 

  16. McCarthy, J.: Circumscription – a form of nonmonotonic reasoning. Artificial Intelligence 13(1&2), 27–39 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  17. Minker, J.: On indefinite data bases and the closed world assumption. In: Loveland, D.W. (ed.) CADE 1982. LNCS, vol. 138, pp. 292–308. Springer, Heidelberg (1982)

    Chapter  Google Scholar 

  18. Muggleton, S., Feng, C.: Efficient induction algorithm. In: [19], pp. 281–298 (1992)

    Google Scholar 

  19. Muggleton, S. (ed.): Inductive Logic Programming. Academic Press, London (1992)

    MATH  Google Scholar 

  20. Muggleton, S.: Inverse entailment and Progol. New Generation Computing 13, 245–286 (1995)

    Article  Google Scholar 

  21. Nienhuys-Cheng, S.-H., de Wolf, R.: Foundations of Inductive Logic Programming. LNCS, vol. 1228. Springer, Heidelberg (1997)

    Google Scholar 

  22. Otero, R.P.: Induction of stable models. In: Rouveirol, C., Sebag, M. (eds.) ILP 2001. LNCS (LNAI), vol. 2157, pp. 193–205. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  23. Osorio, M., Navarro, J.A., Arrazola, J.: Equivalence in answer set programming. In: Pettorossi, A. (ed.) LOPSTR 2001. LNCS, vol. 2372, pp. 57–75. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  24. Plotkin, G.D.: A further note on inductive generalization. In: Meltzer, B., Michie, D. (eds.) Machine Intelligence, vol. 6, pp. 101–124. Edinburgh University Press (1971)

    Google Scholar 

  25. Sagiv, Y.: Optimizing Datalog programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 659–668. Morgan Kaufmann, San Francisco (1988)

    Google Scholar 

  26. Sakama, C.: Induction from answer sets in nonmonotonic logic programs. ACM Transactions on Computational Logic, 6(2):203–231(2005); Preliminary version: Learning by answer sets. In: Proceedings of the AAAI Spring Symposium on Answer Set Programming, pp. 181–187. AAAI Press, Menlo Park (2001)

    Google Scholar 

  27. Yamamoto, A.: Which hypotheses can be found with inverse entailment? In: Džeroski, S., Lavrač, N. (eds.) ILP 1997. LNCS, vol. 1297, pp. 296–308. Springer, Heidelberg (1997)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Communication Sciences, Wakayama University, Sakaedani, Wakayama, 640-8510, Japan

    Chiaki Sakama

  2. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

    Katsumi Inoue

Authors
  1. Chiaki Sakama
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Katsumi Inoue
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institut für Informatik I12, Technische Universität München, Boltzmannstr. 3, D-85748, Garching b. München, Germany

    Stefan Kramer

  2. Department of Computer Science, University of Waikato, Hamilton, New Zealand

    Bernhard Pfahringer

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sakama, C., Inoue, K. (2005). Inductive Equivalence of Logic Programs. In: Kramer, S., Pfahringer, B. (eds) Inductive Logic Programming. ILP 2005. Lecture Notes in Computer Science(), vol 3625. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11536314_19

Download citation

  • DOI: https://doi.org/10.1007/11536314_19

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-28177-1

  • Online ISBN: 978-3-540-31851-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics