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). 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.