Skip to main content
SpringerLink
Log in

Approximating the Semantics of Logic Programs by Recurrent Neural Networks

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

In [1] we have shown how to construct a 3-layered recurrent neural network that computes the fixed point of the meaning function TP of a given propositional logic program P, which corresponds to the computation of the semantics of P. In this article we consider the first order case. We define a notion of approximation for interpretations and prove that there exists a 3-layered feed forward neural network that approximates the calculation of TP for a given first order acyclic logic program P with an injective level mapping arbitrarily well. Extending the feed forward network by recurrent connections we obtain a recurrent neural network whose iteration approximates the fixed point of TP. This result is proven by taking advantage of the fact that for acyclic logic programs the function TP is a contraction mapping on a complete metric space defined by the interpretations of the program. Mapping this space to the metric space R with Euclidean distance, a real valued function fP can be defined which corresponds to TP and is continuous as well as a contraction. Consequently it can be approximated by an appropriately chosen class of feed forward neural networks.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Hölldobler and Y. Kalinke, “Towards a massively parallel computational model for logic programming,” in Proceedings of the ECAI'94 Workshop on Combining Symbolic and Connectionist Processing, ECCAI, 1994, pp. 68-77.

  2. S. Hölldobler, Y. Kalinke, and H.-P. Störr, “Recurrent neural networks to approximate the semantics of acceptable logic programs,” in Advanced Topics in Artificial Intelligence, edited by G. Antoniou and J. Slaney, LNAI 1502, Springer-Verlag, 1998.

  3. S.-E. Bornscheuer, S. Hölldobler, Y. Kalinke, and A. Strohmaier, “Massively parallel reasoning,” Automated Deduction—A Basis for Applications, Kluwer Academic Publishers, vol. II, chap. 11, pp. 291-321, 1998.

  4. P.N. Johnson-Laird and R.M.J. Byrne, Deduction, Lawrence Erlbaum Associates: Hove and London, UK, 1991.

    Google Scholar 

  5. P. Smolensky, “On the proper treatment of connectionism,” Behavioral and Brain Sciences, vol. 11,no. 1, pp. 1-23, 1988.

    Google Scholar 

  6. R. Manthey and F. Bry, “SATCHMO: A theorem prover implemented in Prolog,” in Proceedings of the Conference on Automated Deduction, edited by E. Lusk and R. Overbeek, LLNCS 310, pp. 415-434, Springer, 1988.

  7. M. Fujita, R. Hasegawa, M. Koshimura, and H. Fujita, “Model generation theorem provers on a parallel inference machine,” in Fifth Generation Computer Systems '92: Proceedings of the International Conference on Fifth Generation Computer Systems,” edited by ICOT Staff, IOS Press, pp. 357-375, 1992.

  8. J. Slaney, “Scott: A model-guided theorem prover,” in Proceedings of the International Joint Conference on Artificial Intelligence, 1993, pp. 109-114.

  9. J.W. Lloyd, Foundations of Logic Programming, Springer, 1987.

  10. K.R. Apt and M.H. Van Emden, “Contributions to the theory of logic programming,” Journal of the ACM, vol. 29, pp. 841-862, 1982.

    Google Scholar 

  11. M. Fitting, “Metric methods—three examples and a theorem,” Journal of Logic Programming, vol. 21,no. 3, pp. 113-127, 1994.

    Google Scholar 

  12. A.S. d'Avila Garcez, G. Zaverucha, and L.A.V. de Carvalho, “Logic programming and inductive learning in artificial neural networks,” in Knowledge Representation in Neural Networks, edited by Ch. Herrmann, F. Reine, and A. Strohmaier, Logos Verlag: Berlin, pp. 33-46, 1997.

    Google Scholar 

  13. G.G. Towell and J.W. Shavlik, “Extracting refined rules from knowledge-based neural networks,” Machine Learning, vol. 13,no. 1, pp. 71-101, 1993.

    Google Scholar 

  14. R. Andrews, J. Diederich, and A. Tickle, “A survey and critique of techniques for extracting rules from trained artificial neural networks,” Knowledge-Based Systems, vol. 8,no. 6, 1995.

  15. J. McCarthy, “Epistemological challanges for connectionism,” Behavioural and Brain Sciences, vol. 11, p. 44, 1988, Commentary to [5].

    Google Scholar 

  16. G. Pinkas, “Symmetric neural networks and logic satisfiability,” Neural Computation, vol. 3, 1991.

  17. G. Pinkas, “Expressing first-order logic in symmetric connectionist networks,” in Informal Proceedings of the International Workshop on Parallel Processing for AI, edited by L.N. Kanal and C.B. Suttner, Sydney, Australia, pp. 155-160, Aug. 1991.

  18. L. Shastri and V. Ajjanagadde, “From associations to systematic reasoning: A connectionist representation of rules, variables and dynamic bindings using temporal synchrony,” Behavioural and Brain Sciences, vol. 16,no. 3, pp. 417-494, Sept. 1993.

    Google Scholar 

  19. S. Hölldobler, “Automated inferencing and connectionist models,” Technical Report AIDA-93-06, Intellektik, Informatik, TH Darmstadt, 1993 (Postdoctoral Thesis).

    Google Scholar 

  20. T.E. Lange and M.G. Dyer, “High-level inferencing in a connectionist network,” Connection Science, vol. 1, pp. 181-217, 1989.

    Google Scholar 

  21. J.B. Pollack, “Recursive distributed representations,” Artificial Intelligence, vol. 46, pp. 77-105, 1990.

    Google Scholar 

  22. A. Sperduti, “Labeling RAAM,” Technical Report TR-93-029, International Computer Science Institute, Berkeley, CA, 1993.

    Google Scholar 

  23. T.A. Plate, “Holographic reduced representations,” in Proceedings of the International Joint Conference on Artificial Intelligence, pp. 30-35, 1991.

  24. Y. Kalinke, “Using connectionist term representation for first-order deduction-A critical view,” in Connectionist Systems for Knowledge Representation Deduction, edited by F. Maire, R. Hayward, and J. Diederich, Queensland University of Technology, 1997.

  25. H. Siegelmann and E.D. Sontag, “Turing computability with neural nets,” Applied Mathematics Letters, vol. 4,no. 6, pp. 77-80, 1991.

    Google Scholar 

  26. C.W. Omlin and C.L. Giles, “Extraction of rules from discrete-time recurrent neural networks,” Neural Networks, vol. 9,no. 1, pp. 41-52, 1996.

    Google Scholar 

  27. M. Casey, “The dynamics of discrete-time computation, with application to recurrent neural networks and finite state machine extraction,” Neural Computation, vol. 8,no. 6, pp. 1135-1178, 1996.

    Google Scholar 

  28. N. Alon, A. Dewdney, and T. Ott, “Efficient simulation of finite automata by neural nets,” Journal of the Association for Computing Machinery, vol. 38,no. 2, pp. 495-514, 1991.

    Google Scholar 

  29. C.W. Omlin and C.L. Giles, “Constructing deterministic finite-state automata in recurrent neural networks,” Journal of the ACM, vol. 45,no. 6, pp. 937-972, 1996.

    Google Scholar 

  30. R.L. Watrous and G. Kuhn, “Induction of finite-state automata using second-order recurrent networks,” in Neural Information Processing Systems 4, edited by J.E. Moody et al., Morgan Kaufmann: San Mateo, CA, pp. 309-316, 1992.

    Google Scholar 

  31. C.L. Giles, C. Miller, G.Z. Sun, H.H. Chen, Y.C. Lee, and D. Chen, “Learning and extracting finite state automata with second-order recurrent neural networks,” Neural Computation, vol. 4,no. 3, pp. 393-405, 1992.

    Google Scholar 

  32. P. Frasconi, M. Gori, M. Maggini, and G. Soda, “Representation of finite state automata in recurrent radial basis function networks,” Machine Learning, vol. 23, pp. 5-32, 1996.

    Google Scholar 

  33. J.F. Kolen, “Exploring the computational capabilities of recurrent neural networks,” Ph.D. Thesis, Ohio State University, 1994.

  34. Y. Kalinke and H. Lehmann, “Computation in recurrent neural networks: From counters to iterated function systems,” in Advanced Topics in Artificial Intelligence, edited by G. Antoniou and J. Slaney, LNAI 1502, Springer-Verlag, 1998.

  35. A. Sperduti, “On the computational power of recurrent neural networks,” Neural Networks, vol. 10,no. 3, pp. 395-400, 1997.

    Google Scholar 

  36. S.C. Kremer, “Finite state automata that recurrent cascade-corelation cannot represent,” in Advances in Neural Information Processing Systems 8, edited by D.S. Touretzky et al., MIT Press: Cambridge, MA, pp. 612-618, 1996.

    Google Scholar 

  37. K.-I. Funahashi, “On the approximate realization of continuous mappings by neural networks,” Neural Networks, vol. 2, pp. 183-192, 1989.

    Google Scholar 

  38. K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are universal approximators,” Neuronal Networks, vol. 2, pp. 359-366, 1989.

    Google Scholar 

  39. S. Willard, General Topology, Addison-Wesley, 1970.

  40. L. Cavedon, “Acyclic programs and the completeness of SLDNF-resolution,” Theoretical Computer Science, vol. 86,no. 1, pp. 81-92, 1991.

    Google Scholar 

  41. K.R. Apt and M. Bezem, “Acyclic programs,” Logic Programming, in Proceedings of the Seventh International Conference, edited by D.H.D. Warren and P. Szeredi, MIT Press: Jerusalem, Israel, pp. 617-633, June 1990.

    Google Scholar 

  42. K.R. Apt and M. Bezem, “Acyclic programs,” New Generation Computing, vol. 9,nos. 3/4, pp. 335-363, 1991.

    Google Scholar 

  43. T.C. Przymusinski, “On the declarative semantics of deductive databases and logic programs,” in Foundations of Deductive Databases and Logic Programming, edited by J. Minker, Morgan Kaufmann Publishers Inc.: Los Altos, pp. 193-216, 1988.

    Google Scholar 

  44. A.K. Seda and P. Hitzler, “Topology and iterates in computational logic,” Topology Proceedings, in Proceedings of the Twelveth Summer Conference on General Topology and its Applications: Special Session on Topology in Computer Science, Annals of the New York Academy of Sciences, Ontario, Aug. 1997, Topology Proceedings 22 (1999), pp. 427-429.

    Google Scholar 

  45. A.K. Seda and P. Hitzler, “Strictly level-decreasing logic programs, in Proceedings of the Second Irish Workshop on Formal Methods, edited by A. Butterfield and S. Flynn, Electronic Workshops in Computing, Springer-Verlag, 1998, to appear.

  46. T.A. Plate, “Distributed representations and nested compositional structure,” Ph.D. Thesis, Department of Computer Science, University of Toronto, 1994.

  47. S.-E. Bornscheuer, “Generating rational models,” in Proceedings of the Joint International Conference and Symposium on Logic Programming (JICSLP), edited by M. Maher, MIT Press, p. 547, 1996.

  48. K.L. Clark, “Negation as failure,” in Logic and Databases, edited by H. Gallaire and J. Minker, Plenum: New York, NY, pp. 293-322, 1978.

    Google Scholar 

  49. Devienne and P. Lebégue, A. Parrain, J. C. Routier, and J. Würz, “Smallest Horn Clause Programs,” Journal of Logic Programming, vol. 19,no. 20, pp. 635-679, 1994.

    Google Scholar 

Download references

Authors
  1. Steffen Hölldobler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yvonne Kalinke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hans-Peter Störr
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hölldobler, S., Kalinke, Y. & Störr, HP. Approximating the Semantics of Logic Programs by Recurrent Neural Networks. Applied Intelligence 11, 45–58 (1999). https://doi.org/10.1023/A:1008376514077

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008376514077

Search

Navigation