Document Type

Article

Date

1994

Embargo Period

8-2012

Keywords

locally stratified logic problems, nondeterministic finite register machines

Language

English

Disciplines

Computer Sciences | Mathematics

Description/Abstract

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.

Creative Commons License


This work is licensed under a Creative Commons Attribution 3.0 License.

 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.