Skip to main content
SpringerLink
Log in

The anatomy of vampire

Implementing bottom-up procedures with code trees

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

Abstract

We present an implementation technique for a class of bottom-up logic procedures. The technique is based oncode trees. It is intended to speed up most important and costly operations, such as subsumption and resolution. As an example, we consider the forward subsumption problem which is the bottleneck of many systems implementing first-order logic.

To efficiently implement subsumption, we specialize subsumption algorithms at run time, using theabstract subsumption machine. The abstract subsumption machine makes subsumption-check using sequences of instructions that are similar to the WAM instructions. It gives an efficient implementation of the “clause at a time” subsumption problem. To implement subsumption on the “set at a time” basis, we combine sequences of instructions incode trees.

We show that this technique yields a new way of indexing clauses. Some experimental results are given.

The code trees technique may be used in various procedures, including binary resolution, hyper-resolution, UR-resolution, the inverse method, paramodulation and rewriting, OLDT-resolution, SLD-AL-resolution, bottom-up evaluation of logic programs, and disjunctive logic programs.

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

  • Astrakhan, O. L. and Stickel, M. E.: Caching and lemmaizing in model elimination theorem prover in D. Kapur (ed.),11th Int. Conf. on Automated Deduction, Vol. 607 of Lecture Notes in Artificial Intelligence, Saratoga Springs, NY, June 1992. Springer Verlag, pp. 224–239.

  • Bancilhon, F., Maier, D., Sagiv, Y., and Ullman, J. D.: Magic sets and other strange ways to implement logic programs, inProc. of the 5th ACM SIGMOD-SIGACT Symposium on Principles of Database Systems, Cambridge, MA, March 1986, pp. 1–15.

  • Beeri, C., Naqvi, Sh., Ramakrishnan, R., Shmueli, O., and Tsur, Sh.: Sets and negation in a logic database language (LDL1), inProc. 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, 1987, 21–36.

  • Beeri, C. and Ramakrishnan, R.: On the power of Magic, inProc. 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, 1987, pp. 269–283.

  • Codish, M. and Demoen, B.: Analyzing logic programs using “Prop”-ositional logic programs and a magic wand, in Dale Miller (ed.),Logic Programming — Proc. of the 1993 Int. Symposium, The MIT Press, 1993, pp. 114–129.

  • Das, S. K.:Deductive Databases and Logic Programming, Addison-Wesley, 1992.

  • Decker, H.: Integrity enforcements on deductive databases, inProc. of the 1st Int. Conf. on Expert Database Systems, Charleston, South Carolina, April 1986, pp. 271–285.

  • Garey, M. R. and Johnson, D. S.:Computers and Intractability, Freeman, San Francisco, 1979.

    Google Scholar 

  • Goller, C., Letz, R., Mayr, K., and Schumann, J.: SETHEO V3.2: Recent developments, in A. Bundy (ed.),Automated Deduction — CADE-12. 12th Int. Conf. on Automated Deduction, Vol. 814 of Lecture Notes in Artificial Intelligence, Nancy, France, June/July 1994, pp. 778–782.

  • Gottlob, G. and Leitsch, A.: On the efficiency of subsumption algorithms,J. Association for Computing Machinery 32(2) (1987), 280–295.

    Google Scholar 

  • Graf, P.: Extended path-indexing, in A. Bundy (ed.),Automated Deduction — CADE-12. 12th Int. Conf. on Automated Deduction, Vol. 814 of Lecture Notes in Artificial Intelligence, Nancy, France, June/July 1994, pp. 514–528.

  • Lusk, E. L.: Controlling redundancy in large search spaces: Argonne-style theorem proving through the years, in A. Voronkov (ed.),Logic Programming and Automated Reasoning. International Conference LPAR'92, Vol. 624 of Lecture Notes in Artificial Intelligence, St. Petersburg, Russia, July 1992, pp. 96–106.

  • Lloyd, J. W., Sonenberg, E. A., and Topor, R. W.: Integrity constraint checking in stratified databases. Technical Report 86/5, Department of Computer Science, University of Melbourne, 1986.

  • Lloyd, J. W. and Topor, R. W.: A basis for deductive database systems,J. Logic Programming 2(2) (1985), 93–109.

    Google Scholar 

  • Maeda, A. M., Aoe, J.-I., and Tomabechi, H.: Signature-check based unification filter,Software — Practice and Experience 24(7) (1994), 603–622.

    Google Scholar 

  • Manthey, R. and Bry, F.: SATCHMO: A theorem prover implemented in Prolog, inCADE'88 (9th Int. Conf. on Automated Deduction), Lecture Notes in Computer Science, Argonne, IL, May 1988, pp. 179–216.

    Google Scholar 

  • Maslov, S. Yu.: An inverse method for establishing deducibility of nonprenex formulas of the predicate calculus, in J. Siekmann and G. Wrightson (eds),Automation of Reasoning (Classical Papers on Computational Logic), Vol. 2, Springer Verlag, 1983, pp. 48–54.

  • McCharen, J., Overbeek, R., and Wos, L.: Complexity and related enhancements for automated theorem-proving programs,Computers and Mathematics with Applications 2 (1976), 1–16.

    Google Scholar 

  • McCharen, J., Overbeek, R., and Wos, L.: Problems and experiments for and with automated theorem-proving programs,IEEE Transactions on Computers C-25(8) (1976), 773–782.

    Google Scholar 

  • McCune, William W.: An indexing method for finding more general formulas,Association for Automated Reasoning Newsletter 1(9) (1988), 7–8.

    Google Scholar 

  • McCune, William W.: OTTER 2.0 users guide. Technical report, Argonne National Laboratory, March 1990.

  • McCune, William W.: Experiments with discrimination-tree in indexing and path indexing for term retrieval,J. Automated Reasoning 9(2) (1992), 147–167.

    Google Scholar 

  • Neiman, V.: Refutation search for born sets by a subgoal-extraction method,J. Logic Programming 9(2) (1990), 267–284.

    Google Scholar 

  • Overbeek, R.: An implementation of hyper-resolution,Computers and Mathematics with Applications 1 (1975), 201–214.

    Google Scholar 

  • Pelletier, F. J.: Seventy-five problems for testing automatic theorem provers,J. Automated Reasoning 2(2) (1986), 191–216.

    Google Scholar 

  • Robinson, J. A.: Automatic deduction with hyper-resolution,Int. J. Computer Mathematics 1 (1965), 227–234.

    Google Scholar 

  • Robinson, J. A.: A machine-oriented logic based on the resolution principle,J. the Association for Computing Machinery 12(1) (1965), 23–41.

    Google Scholar 

  • Robinson, G. and Wos, L. T.: Paramodulation and theorem-proving in first order theories with equality, inMachine Intelligence, Vol. 4. Edinburgh University Press, Edinburgh, 1969.

    Google Scholar 

  • Stickel, M.: A PROLOG technology theorem prover: Implementation by an extended Prolog compiler,J. Automated Reasoning (4) (1988), 353–380.

  • Stickel, M.: The path indexing method for indexing terms. Technical Report 473, Artificial Intelligence Center, SRI International, Menlo Park, Calif., October 1989.

    Google Scholar 

  • Sudarshan, S. and Ramakrishnan, R.: Optimizations of bottom-up evaluation with non-ground terms (extended abstract), in Dale Miller (ed.),Logic Programming. Proc. of the 1993 Int. Symp., The MIT Press, 1993, pp. 557–574.

  • Tambe, M. and Rosenbloom, P. S.: Investigating production system representations for non-combinatorial match,Artificial Intelligence 68 (1994), 155–190.

    Google Scholar 

  • Tamaki, H. and Sato, T.: OLDT resolution with tabulation, inInt. Conf. on Logic Programming, 1986, pp. 84–98.

  • Vieille, Laurent: Recursive query processing: The power of logic,Theoretical Computer Science 69 (1989), 1–53.

    Google Scholar 

  • Voronkov, A.: LISS — The Logic Inference Search System, in Mark Stickel (ed.),Proc. Int. Conf. on Automated Deduction, Vol. 449 of Lecture Notes in Computer Science, Kaiserslautern, Germany, 1990. Springer Verlag, pp. 677–678.

  • Voronkov, A.: Theorem proving in non-standard logics based on the inverse method, in D. Kapur (ed.),11th Int. Conf. on Automated Deduction, Vol. 607 of Lecture Notes in Artificial Intelligence, Saratoga Springs, NY, USA, June 1992. Springer Verlag, pp. 648–662.

  • Warren, David H. D.: An abstract Prolog instruction set. SRI Tech. Note 309, SRI Intl., Menlo Park, Calif., 1983.

  • Warren, D. S.: Memoing for logic programs,Communications of the ACM 35(3) (1992), 93–111.

    Google Scholar 

  • Wos, Larry, Overbeek, Ross, and Lusk, Ewing: Subsumption, a sometimes undervalued procedure, in Jean-Louis Lassez and Gordon Plotkin (eds),Computational Logic. Essays in Honor of Alan Robinson, The MIT Press, Cambridge, MA, 1991, pp. 3–40.

    Google Scholar 

  • Wos, Larry: Note on McCune's article on discrimination trees,J. Automated Reasoning 9(2) (1992), 145–146.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computing Science Department, Uppsala University, Sweden

    Andrei Voronkov

Authors
  1. Andrei Voronkov
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by Swedish TFR grant No. 93–409

Rights and permissions

Reprints and permissions

About this article

Cite this article

Voronkov, A. The anatomy of vampire. J Autom Reasoning 15, 237–265 (1995). https://doi.org/10.1007/BF00881918

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation