The Degree of Unsolvability of the Completion Semantics for General Logic Programs
Levon Haykazyan · Mathematical Problems of Computer Science · 2012
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.