A syntactical analysis of non-size-increasing polynomial time computation
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
20 pages (latex), revised submission (expanded proofs, extended references, new section on tree iteration)
20 pages (latex), revised submission (expanded proofs, extended references, new section on tree iteration)