Title :
A syntactical analysis of non-size-increasing polynomial time computation
Author :
Aehlig, Klaus ; Schwichtenberg, Helmut
Author_Institution :
Inst. of Math., Ludwig-Maximilians-Univ., Munchen, Germany
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
Keywords :
computational complexity; lambda calculus; type theory; affine linear typed lambda calculus; explicit polynomial bounds; functions; polynomial time computation; syntactical analysis; Data structures; Polynomials; Postal services; Size measurement; Sorting; Upper bound;
Conference_Titel :
Logic in Computer Science, 2000. Proceedings. 15th Annual IEEE Symposium on
Conference_Location :
Santa Barbara, CA
Print_ISBN :
0-7695-0725-5
DOI :
10.1109/LICS.2000.855758
