2000/11/30 by Klaus Aehlig, Helmut Schwichtenberg
Computer Science · #cs.LO
published as ACM Transactions on Computational Logic 3(3), 383-401 (2002) · 20 pages (latex), revised submission (expanded proofs, extended references, new section on tree iteration)
arxiv created 2001/09/14 · arxiv updated 2009/11/30
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.