A PSPACE-Complete First Order Fragment of Computability Logic

Details A PSPACE-Complete First Order Fragment of Computability Logic A PSPACE-Complete First Order Fragment of Computability Logic

2012-01-23

arxiv.org/abs/1201.4856v2

Computer Science

Logic in Computer Science

Scientific paper

In a recently launched research program for developing logic as a formal theory of (interactive) computability, several very interesting logics have been introduced and axiomatized. These fragments of the larger Computability Logic aim not only to describe "what" can be computed, but also provide a mechanism for extracting computational algorithms from proofs. Among the most expressive and fundamental of these is CL4, known to be (constructively) sound and complete with respect to the underlying computational semantics. Furthermore, the fragment of CL4 not containing blind quantifiers was shown to be decidable in polynomial space. The present work extends this result and proves that this fragment is, in fact, PSPACE-complete.

Affiliated with

Also associated with

No associations

Rating

A PSPACE-Complete First Order Fragment of Computability Logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A PSPACE-Complete First Order Fragment of Computability Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A PSPACE-Complete First Order Fragment of Computability Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105183