Back to Search Start Over

Polynomial time in untyped elementary linear logic.

Authors :
Laurent, Olivier
Source :
Theoretical Computer Science. Apr2020, Vol. 813, p117-142. 26p.
Publication Year :
2020

Abstract

We show how to represent polynomial time computation in an untyped version of proof-nets for elementary linear logic. This follows previous work by P. Baillot but which was developed in a typed and affine setting. We describe how these two properties can be adapted. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*POLYNOMIAL time algorithms
*LOGIC
*TARDINESS
*COMPUTATIONAL complexity

Details

Language :
English
ISSN :
03043975
Volume :
813
Database :
Academic Search Index
Journal :
Theoretical Computer Science
Publication Type :
Academic Journal
Accession number :
141944190
Full Text :
https://doi.org/10.1016/j.tcs.2019.10.002
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details