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

arrow_drop_up

Comments

Sign up or login to leave a comment