Abstract
This paper presents a linear resolution strategy (GDFC-resolution) for definite logic programs in which goal-directed forward chaining is used to find refutations. GDFC-resolution focuses on relevant facts and rules by means of query independent link clauses. One problem is, that the number of link clauses may be infinite if the program contains recursive rules defined over recursive data structures. We present an approach to generate a more general but finite set of link clauses. We show that GDFC-resolution is sound and complete for definite programs. We discuss the efficiency of GDFC-resolution comparing it with SLD-resolution and present some experimental results.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burgard, W. Generating a Data Structure for Goal-Directed Forward Chaining in Logic Programming. Tech. Rept. 331, Department of Computer Science, University of Dortmund, 1989.
Burgard, W. Goal-Directed Forward Chaining: A Linear Resolution Strategy. Tech. Rept. 360, Department of Computer Science, University of Dortmund, 1990.
Burgard, W. and Heusch, P. Complexity Results on Generating Link Clauses for Goal-Directed Forward Chaining in Logic Programming. In Proceedings of the Second PROTOS Workshop, Sils Maria, Switzerland, Appelrath, H.J., Cremers, A.B., and Herzog, O., 1990.
Chang, C.L. and Lee, R.C.T. Symbolic Logic and Mechanical Theorem Proving, Academic Press(1973).
Garey, M.R. and Johnson, D.S. Computers and Intractability: A Guide to NP-Completeness, W. H. Freeman and Company, San Francisco(1979).
Heidelbach, M. Special Problems with Forward-Chaining Logic Programs, Diploma thesis, In German, University of Dortmund, 1990.
Lassez, J.L., Maher, M.J., and Mariott, K. Unification Revisited. In Deductive Databases and Logic Programming. Morgan Kaufmann Publishers, Inc., Los Altos, California, pp. 587–626, 1987.
Lloyd, J.W. Foundations of Logic Programming, Second, Extended Edition, Springer Verlag(1987).
Lozinskii, E.L. Evaluating Queries in Deductive Databases by Generating. In IJCAI 85 Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Aravind, J., Morgan Kaufmann Publishers, Inc., Los Altos, California, 1985.
Magura, N. An Experimental Study to Estimate the Efficiency of Goal-Directed Forward Chaining, Diploma thesis, In German, University of Dortmund, 1991.
Matsumo, Y., Tanaka, H., Hirakawa, H., Miyoshi, H., and Yasukawa, H. BUP: A Bottom-Up Parser Embedded in Prolog. New Generation Computing 1, 2 (1983), 145–158.
Plümer, L. Termination Proofs for Logic Programs, Springer Verlag, Lecture Notes in Artificial Intelligence, 446(1990).
Rosen, B.K. Robust Linear Algorithms for Cutsets. Journal of Algorithms 3(1982).
Speckenmeyer, E. On Feedback Problems in Digraphs. In Proceedings of the Fifteenth Workshop on Graphs, Rolduc, Netherlands, Springer Verlag, 1989.
Yamamoto, A. and Tanaka, H. Translating Production Rules into a Forward Reasoning Prolog Program. New Generation Computing 4(1986), 97–105.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Burgard, W. (1991). Efficiency considerations on goal-directed forward chaining for logic programs. In: Börger, E., Kleine Büning, H., Richter, M.M., Schönfeld, W. (eds) Computer Science Logic. CSL 1990. Lecture Notes in Computer Science, vol 533. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54487-9_53
Download citation
DOI: https://doi.org/10.1007/3-540-54487-9_53
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54487-6
Online ISBN: 978-3-540-38401-4
eBook Packages: Springer Book Archive