The Degree of Unsolvability of the Completion Semantics for General Logic Programs
Abstract
The completion semantics considers interpretations that satisfy a special first-order theory was first introduced in [1]. These interpretations include but are not limited to Herbrand interpretations. Nevertheless, in logic programming the restriction to Herbrand interpretations is very desirable. As [2] remarks, however, this results in a non-recursively enumerable semantics. In this paper we show the П 11 -completeness of the completion semantics with restriction to Herbrand interpretations.
References
K.L.Clark, “Negation as failure", In H. Gallaire, J. Minker, Logic and Databeses, pp. 293-323, Plenum, 1978.
J.C. Shepherdson, “Negation as failure, completion and stratification", In D.M. Gabbay, C.J. Hogger, J.A. Robinson, Logic Programming, pp. 355-419, Clarendon Press, 1998.
J.W. Lloyd, R.W. Topor, “Making prolog more expressive", Journal of Logic Programming, vol. 1, pp. 225-240, 1984.
J.W. Lloyd, Foundations of Logic Programming, Springer-Verlag, 1994.
H. Rogers, The Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
