A New Term Rewriting Characterisation of ETIME functions
classification
💻 cs.LO
cs.CC
keywords
etimefunctionsordercomputablereductionrewritingtermadopting
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.