Document Type
Report
Date
7-1991
Embargo Period
5-2-2012
Keywords
logic programming
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
Cholak, Peter and Blair, Howard A., "The Complexity of Local Stratification" (1991). Electrical Engineering and Computer Science Technical Reports. Paper 106.
http://surface.syr.edu/eecs_techreports/106
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-27