Document Type
Article
Date
1995
Keywords
locally stratified programs, hyperarithmetic set
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 defined 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 hyper- arithmetic hierarchy in the same way as Horn logic is to the class of recursively enumerable sets. In particular, a set is definable in the well-founded semantics by a program P whose well-founded partial model is total iff it is hyperarithmetic.
Recommended Citation
Blair, Howard A.; Marek, Wiktor; and Schlipf, John S., "The expressiveness of locally stratified programs" (1995). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 40.
https://surface.syr.edu/lcsmith_other/40
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
