On a Correspondence between Predicative Recursion and Register Machines
12th Workshop on Termination (WST), 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