Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Compiling bottom-up and mixed derivations into top-down executable logic programs

  • Published:
Journal of Automated Reasoning Aims and scope Submit manuscript

Abstract

We present a technique for the compilation of bottom-up and mixed logic derivations into PROLOG-programs. It is obtained as an extension of a program transformation technique called Compiling Control. We illustrate its applications in three different domains: solving numerical problems, integrity checking in deductive databases and theorem proving. The aim is to obtain efficient PROLOG programs for problems in which a non-top-down control is most appropriate.

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

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Bruynooghe, M., DeSchreye, D., and Krekels, B., ‘Compiling control’, J. Logic Programming, 6 135–162 (1989).

    Google Scholar 

  2. VanHentenryck, P., Constraint Satisfaction in Logic Programming, Logic Programming Series, MIT Press, Cambridge, 1989.

    Google Scholar 

  3. De Schreye, D. and Bruynooghe, M., ‘The compilation of forward checking regimes through metainterpretion and transformation’, in Meta-programming in Logic Programming, H. Abramson and M. H. Rogers (Eds.) MIT Press, 1989, pp. 217–231.

  4. Bruynooghe, M., De Raedt, L., and De Schreye, D., ‘Explanation based program transformation’, in Proc. IJCAI'89, 1989, Detroit, pp. 407–412.

  5. Debray, S. K., ‘Unfold/fold transformations and loop optimization of logic programs’, in Proc. SIGPLAN'88 Conf. on Programming Language Design and Implementation, SIGPLAN Notices, Vol. 23, No. 7, July 1988, pp. 297–307.

  6. Kowalski, R., Sadri, F., and Soper, P., ‘Integrity checking in deductive databases’, in Proc. 13th VLDB, Brighton, England, 1987.

  7. Sadri, F. and Kowalski, R., ‘A theorem-proving approach to database integrity’, in Foundations of Deductive Databases and Logic Programming, J. Minker, Morgan Kaufmann Publishers, 1988, pp. 313–362.

  8. Soper, P. J. R., Integrity Checking in Deductive Databases, M.Sc. Thesis, Department of Computing, Imperial College, London, 1986.

  9. Mitchell, T. M., Keller, R. M., and Kedar-Cabelli, S. T., ‘Explanation-based generalization: a unifying view’, Machine Learning, 1, 47–80 (1986).

    Google Scholar 

  10. DeJong, G. and Mooney, R., ‘Explanation-based learning: an alternative view’, Machine Learning, 1, 145–176 (1986).

    Google Scholar 

  11. DeSchreye, D. and Bruynooghe, M., ‘On the transformation of logic programs with instantiation based computation rules’, J. Symbolic Computation, 7, 125–154 (1989).

    Google Scholar 

  12. Debray, S. K. and Warren, D. S., ‘Detection and optimization of functional computations’ in Prolog, Proceedings Third International Logic Programming Conference, LNCS, 225, Springer-Verlag, 1988, pp. 490–504.

  13. Kanamori, T., Horiuchi, K., and Kawamura, T., ‘Detecting functionality of logic programs based on abstract hybrid interpretation’, ICOT Technical Report, TR 331, 1988.

  14. Clocksin, W. F., ‘A technique for translating clausal specifications of numerical methods into efficient programs’, J. Logic Programming, 5 (3), 231–242 (1988).

    Google Scholar 

  15. Burstall, R. M. and Darlington, J. ‘A transformation system for developing recursive programs’, JACM, 24, 44–67 (1977).

    Google Scholar 

  16. Debray, S. K., Global Optimization of Logic Programs, Ph.D. dissertation, Stony Brook, 1986.

  17. Bruynooghe, M. and De Schreye, D., ‘Some thoughts on the role of examples in program transformation and its relevance for explanation based learning’, in Proc. International Workshop on Analogical and Inductive Inference, (AII89), LNCS, 397, Springer-Verlag, 1989, pp. 60–78.

  18. Decker, H. Integrity enforcement on deductive databases’, in Proc. First International Conference on Expert Database Systems, Charleston, South Carolina, USA, 1986.

  19. Lloyd, J. W., Sonenberg, E. A., and Topor, R. W., ‘Integrity checking in stratified databases’, J. Logic Programming, 4, 331–343 (1987).

    Google Scholar 

  20. Bry, F., Decker, H., and Manthey, R., ‘A uniform approach to constraint satisfaction and constraint satisfiability in deductive databases’, in Proc. EDBT'88, Venice, Italy, 1988.

  21. Ramsay, A., Formal Methods in Artificial Intelligence, Cambridge University Press, 1988.

Download references

Author information

Authors and Affiliations

Authors

Additional information

Work partly supported by ESPRIT BRA COMPULOG (project 3012).

Supported by the Belgian I.W.O.N.L.-I.R.S.I.A. under contract number 5203. Author for correspondence.

Supported by the Belgian National Fund for Scientific Research.

Rights and permissions

Reprints and permissions

About this article

Cite this article

De Schreye, D., Martens, B., Sablon, G. et al. Compiling bottom-up and mixed derivations into top-down executable logic programs. J Autom Reasoning 7, 337–358 (1991). https://doi.org/10.1007/BF00249018

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00249018

Key words

Navigation