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