A New Term Rewriting Characterisation of ETIME functions

Martin Avanzini, Naohi Eguchi

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.

Knowledge Graph



Sign up or login to leave a comment