A syntactical analysis of non-size-increasing polynomial time computation

Simple item page
dc.creatorAehlig, Klaus
dc.creatorSchwichtenberg, Helmut
dc.date2000-11-23
dc.date2001-09-14
dc.date.accessioned2026-07-07T03:16:45Z
dc.date.available2026-07-07T03:16:45Z
dc.descriptionA 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.
dc.description20 pages (latex), revised submission (expanded proofs, extended references, new section on tree iteration)
dc.identifierhttps://arxiv.org/abs/cs/0011037
dc.identifierhttp://arxiv.org/abs/cs/0011037
dc.identifierACM Transactions on Computational Logic 3(3), 383-401 (2002)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30474
dc.subjectLogic in Computer Science
dc.subjectF.4.1; F.2.2
dc.titleA syntactical analysis of non-size-increasing polynomial time computation
dc.typetext

Files

Collections

arXiv