On a Correspondence between Predicative Recursion and Register Machines
>
Proceedings of the 12th Workshop on Termination, pages 15–19, 2012.>
>
>
Abstract
In this abstract we give a precise characterisation of polynomial time (wrt. register machines) via small polynomial path orders.
Categories
Term Rewriting, Complexity Analysis, ICC, Predicative Recursion