THE COMPLEXITY OF LOCAL STRATIFICATION

Article type: Research Article

Authors: Cholak, Peter | Blair, Howard A.

Affiliations: Mathematical Sciences Institute, Cornell University, Ithaca, New York 14850, USA | School of Computer and Information Science, Syracuse University, Syracuse, New York 13244-4100, USA

Note: [] Research supported in part by the Army Research Office through the Mathematical Sciences Institute of Cornell University.

Note: [] Research supported in part by the Army Research Office through the Mathematical Sciences Institute of Cornell University and by the Systems Sciences Laboratory of the Xerox Corporation's Webster Research Center. blair@top.cis.syr.edu

Abstract: The class of locally stratified logic programs is shown to be Pi-1-1 complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.

DOI: 10.3233/FI-1994-2144

Journal: Fundamenta Informaticae, vol. 21, no. 4, pp. 333-344, 1994