The class of locally stratified logic programs is shown to be Π11-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.nondeterministic finite register machines.
Cholak, Peter and Blair, Howard A., "The Complexity of Local Stratification" (1991). Electrical Engineering and Computer Science - Technical Reports. 106.
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.