A New Term Rewriting Characterisation of ETIME functions
Martin Avanzini, Naohi Eguchi · arXiv (Cornell University) · 2013
Adopting former term rewriting characterisations of polytime and exponential-time computable functions, we introduce a new reduction order, the Path Order for ETIME (POE* for short), that is sound and complete for ETIME computable functions. The proposed reduction order for ETIME makes contrasts to those related complexity classes clear.