Document Type
Report
Date
1-1992
Keywords
logic programming
Language
English
Disciplines
Computer Sciences
Description/Abstract
This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be computed by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs does not increase when one considers the programs which have a unique stable model or a total well-founded model. This shows that all these classes of structures (perfect models of locally stratified logic programs, well-founded models which turn out to be total, and stable models of programs possessing a unique stable model) are all closely connected with Kleene's hyperarithmetical hierarchy. Thus, for general logic programming, negation with respect to two-valued logic is related to the hyperarithmetic hierarchy in the same way as Horn logic is to the class of recursively enumerable sets.
Recommended Citation
Blair, Howard A.; Marek, Wiktor; and Schlipf, John S., "The Expressiveness of Locally Stratified Programs" (1992). Electrical Engineering and Computer Science - Technical Reports. 105.
https://surface.syr.edu/eecs_techreports/105
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-28