Abstract
We propose a new realization of goal-directed query evaluation of (non-floundering) normal logic programs for the well-founded semantics. To this end we introduce a new magic templates transformation and give a new fixed point characterization of the well-founded semantics, lifting an existing definition from the ground to the non-ground case. The new fixed point characterization enables us to show a step-by-step correspondence between the naive bottom-up evaluation of the transformed program and a class of top-down search strategies defined in terms of the search forest framework of Bol and Degerstedt. This correspondence implies that the magic transformation is sound and complete. Hence, it provides an upper bound on the search space that must be considered in order to preserve completeness of the bottom-up approach.
Preview
Unable to display preview. Download preview PDF.
References
Krzysztof Apt and Roland Bol. Logic Programming and Negation: A Survey. J. of Logic Programming, 19/20:9–71, 1994.
Krzysztof Apt. Introduction to Logic Programming. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Formal Models and Semantics, volume B, chapter 10, pages 493–574. Elsevier, 1990.
R. Bol and L. Degerstedt. Tabulated Resolution for Well Founded Semantics. In Proc. of the International Logic Programming Symposium, Vancouver, pages 199–219. The MIT Press, 1993.
R. Bol and L. Degerstedt. The Underlying Search for Magic Templates and Tabulation. In Proc. of International Conf. on Logic Programming, Budapest, pages 793–811. The MIT Press, 1993.
S. Brass and J. Dix. A General Approach to Bottom-up Computation of Disjunctive Semantics. pages 127–155, this volume
S. Bonnier, U. Nilsson, and T. Näslund. A Simple Fixed Point Characterization of Three-valued Stable Model Semantics. Information Processing Letters, 40(2):73–78, 1991.
W. Chen and D. S. Warren. Query Evaluation under the Well-founded Semantics. In Proc. of SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 168–179, Washington DC, 1993.
W. Chen and D.S. Warren. Computation of Stable Models and its Integration with Logical Query Processing. Technical report, Comp. Sci. Dept, SUNY ant Stony Brook, 1993.
L. Degerstedt. Tabulated Resolution for Well-Founded Semantics. Licentiate thesis no 402, Dept. of Computer and Information Science, Linköping University, 1993.
D. Kemp, P. Stuckey, and D. Srivastava. Magic Sets and Bottom-up Evaluation of Well-founded Models. In Proc. of 1991 International Logic Programming Symposium, San Diego, pages 337–351. The MIT Press, 1991.
D. Kemp, P. Stuckey, and D. Srivastava. Query Restricted Bottom-up Evaluation of Normal Logic Programs. In K. Apt, editor, Proc. of Joint International Conf. and Symp. on Logic Programming, Washington, pages 288–302. The MIT Press, 1992.
John W. Lloyd. Foundations of Logic Programming. Springer-Verlag, second edition, 1987.
J. Lloyd and J. Shepherdson. Partial Evaluation in Logic Programming. J. of Logic Programming, 11(3–4):217–242, 1991.
S. Morishita. An Alternating Fixpoint Tailored to Magic Programs. In Proc. of SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 123–134, Washington DC, 1993.
U. Nilsson. Goal-directed Bottom-up Evaluation of Normal Logic Programs. In Proc. of the International Logic Programming Symposium, Vancouver, 1993. The MIT Press. (Abstract).
T. Przymusinski. Every Logic Program has a Natural Stratification and an Iterated Fixed Point Model. In Proc. of the 8th Symposium on Principles of Database Systems, pages 11–21, 1989.
T. Przymusinski. The Well-founded Semantics Coincides with the Three-valued Stable Semantics. Fundamenta Informaticae, 13(4):445–464, 1990.
T. Przymusinski and D. S. Warren. Well Founded Semantics: Theory and Implementation. Draft, 1992.
R. Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic Programming. In Proc. of Fifth International Conf/Symposium on Logic Programming, Seattle, pages 140–159. The MIT Press, 1988.
K. Ross. A Procedural Semantics for Well-founded Negation in Logic Programs. J. of Logic Programming, 13(1):1–22, 1992.
H. Tamaki and T. Sato. OLD Resolution with Tabulation. In E Shapiro, editor, Proc. of Third International Conf. on Logic Programming, London, Lecture Notes in Computer Science 225, pages 84–98. Springer-Verlag, 1986.
A. Van Gelder, K. Ross, and J. Schlipf. The Well-Founded Semantics for General Logic Programs. J. of the ACM, 38(3):620–650, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Degerstedt, L., Nilsson, U. (1995). Magic computation for well-founded semantics. In: Dix, J., Pereira, L.M., Przymusinski, T.C. (eds) Non-Monotonic Extensions of Logic Programming. NMELP 1994. Lecture Notes in Computer Science, vol 927. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030665
Download citation
DOI: https://doi.org/10.1007/BFb0030665
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59467-3
Online ISBN: 978-3-540-49272-6
eBook Packages: Springer Book Archive