15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 4 - Mathematische Logik, Theoretische Informatik
Donnerstag, 20. September 2001, 16.00, Hörsaal 46

 

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

Helmut Schwichtenberg , Universität München (Koautor: Klaus Aehlig)

 

A purely 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 also gives explicit polynomial bounds that can easily be calculated.

E-Mail:	schwicht@rz.mathematik.uni-muenchen.de
Homepage:	www.mathematik.uni-muenchen.de/~schwicht/

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden