The Complexity of Local Stratification
Peter A. Cholak, Howard A. Blair · 1991
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.