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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.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.
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.
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.
Maeda, A. M., Aoe, J.-I., and Tomabechi, H.: Signature-check based unification filter,Software — Practice and Experience 24(7) (1994), 603–622.
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.
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.
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.
McCune, William W.: An indexing method for finding more general formulas,Association for Automated Reasoning Newsletter 1(9) (1988), 7–8.
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.
Neiman, V.: Refutation search for born sets by a subgoal-extraction method,J. Logic Programming 9(2) (1990), 267–284.
Overbeek, R.: An implementation of hyper-resolution,Computers and Mathematics with Applications 1 (1975), 201–214.
Pelletier, F. J.: Seventy-five problems for testing automatic theorem provers,J. Automated Reasoning 2(2) (1986), 191–216.
Robinson, J. A.: Automatic deduction with hyper-resolution,Int. J. Computer Mathematics 1 (1965), 227–234.
Robinson, J. A.: A machine-oriented logic based on the resolution principle,J. the Association for Computing Machinery 12(1) (1965), 23–41.
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.
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.
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.
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.
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.
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.
Wos, Larry: Note on McCune's article on discrimination trees,J. Automated Reasoning 9(2) (1992), 145–146.
Author information
Authors and Affiliations
Additional information
Supported by Swedish TFR grant No. 93–409
Rights 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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00881918