Title of article :
Higher type recursion, ramification and polynomial time
Original Research Article
Author/Authors :
Stephen J. Bellantoni، نويسنده , , Karl-Heinz Niggl، نويسنده , , Helmut Schwichtenberg، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2000
Abstract :
It is shown how to restrict recursion on notation in all finite types so as to characterize the polynomial-time computable functions. The restrictions are obtained by using a ramified type structure, and by adding linear concepts to the lambda calculus.
Keywords :
Polynomial time , Higher type recursion , Lambda calculus , Normalisation , Ramified recursion
Journal title :
Annals of Pure and Applied Logic
Journal title :
Annals of Pure and Applied Logic
