Light affine set theory: A naive set theory of polynomial time

Studia Logica 77 (1):9 - 40 (2004)
Abstract
In [7], a naive set theory is introduced based on a polynomial time logical system, Light Linear Logic (LLL). Although it is reasonably claimed that the set theory inherits the intrinsically polytime character from the underlying logic LLL, the discussion there is largely informal, and a formal justification of the claim is not provided sufficiently. Moreover, the syntax is quite complicated in that it is based on a non-traditional hybrid sequent calculus which is required for formulating LLL.In this paper, we consider a naive set theory based on Intuitionistic Light Affine Logic (ILAL), a simplification of LLL introduced by [1], and call it Light Affine Set Theory (LAST). The simplicity of LAST allows us to rigorously verify its polytime character. In particular, we prove that a function over {0, 1}* is computable in polynomial time if and only if it is provably total in LAST.
Keywords Philosophy   Logic   Mathematical Logic and Foundations   Computational Linguistics
Categories (categorize this paper)
DOI 10.1023/B:STUD.0000034183.33333.6f
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,370
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
Stability and Paradox in Algorithmic Logic.Wayne Aitken & Jeffrey A. Barrett - 2006 - Journal of Philosophical Logic 36 (1):61 - 95.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Unifying Sets and Programs Via Dependent Types.Wojciech Moczydłowski - 2012 - Annals of Pure and Applied Logic 163 (7):789-808.

Add more citations

Similar books and articles
Added to PP index
2009-01-28

Total downloads
15 ( #322,972 of 2,193,784 )

Recent downloads (6 months)
1 ( #290,983 of 2,193,784 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature