Name
Abstract | ||
|---|---|---|
A purely syntactical proof is given that all functions definable in a certain affine linear typed λ-calculus with iteration in all types are polynomial time computable. The proof also gives explicit polynomial bounds that can easily be calculated |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1145/507382.507386 | ACM Transactions on Computational Logic (TOCL) |
Keywords | DocType | Volume |
lambda calculus,syntactical analysis,linear logic,complexity,syntactical proof,polynomial time computable,non-size-increasing polynomial time computation,polynomial time computation,explicit polynomial bound,functions definable,computational complexity,sorting,polynomial time,polynomials,upper bound,functions,type system,syntactic analysis,data structures,type theory | Journal | 3 |
Issue | ISSN | ISBN |
3 | 1043-6871 | 0-7695-0725-5 |
Citations | PageRank | References |
15 | 1.85 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Klaus Aehlig | 1 | 123 | 12.08 |
| Helmut Schwichtenberg | 2 | 373 | 44.83 |