On the complexity of stratified logics

Details On the complexity of stratified logics On the complexity of stratified logics

2010-02-18

arxiv.org/abs/1002.3453v1

Computer Science

Computational Complexity

PhD thesis. about 180 pages

Scientific paper

Our primary motivation is the comparison of two different traditions used in ICC to characterize the class FPTIME of the polynomial time computable functions. On one side, FPTIME can be captured by Intuitionistic Light Affine Logic (ILAL), a logic derived from Linear Logic, characterized by the structural invariant Stratification. On the other side, FPTIME can be captured by Safe Recursion on Notation (SRN), an algebra of functions based on Predicative Recursion, a restriction of the standard recursion schema used to defiine primitive recursive functions. Stratifiication and Predicative Recursion seem to share common underlying principles, whose study is the main subject of this work.

Affiliated with

Also associated with

No associations

Rating

On the complexity of stratified logics 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 On the complexity of stratified logics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of stratified logics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-404998