Document Type
Article
Date
1994
Keywords
locally stratified logic problems, nondeterministic finite register machines
Language
English
Disciplines
Computer Sciences | Mathematics
Description/Abstract
The class of locally stratified logic programs is shown to be Π 1 1-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.
Recommended Citation
Cholak, Peter and Blair, Howard A., "The Complexity of Local Stratification" (1994). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 17.
https://surface.syr.edu/lcsmith_other/17
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
