locally stratified logic problems, nondeterministic finite register machines
Computer Sciences | Mathematics
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.
Cholak, Peter and Blair, Howard A., "The Complexity of Local Stratification" (1994). L.C. Smith College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. Paper 17.
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.