A syntactical analysis of non-size-increasing polynomial time computation
classification
💻 cs.LO
keywords
polynomialproofsyntacticaltimeaffineanalysisboundscalculated
read the original abstract
A syntactical proof is given that all functions definable in a certain affine linear typed lambda-calculus with iteration in all types are polynomial time computable. The proof provides explicit polynomial bounds that can easily be calculated.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.