A Path Order for Rewrite Systems that Compute Exponential Time Functions
Proceedings of the 22nd International Conference on Rewriting Techniques and Applications, volume 10 of Leibnitz International Proceedings in Informatics, pages 123–138, 2011.
© Creative Commons License - ND
Abstract
In this paper we present a new path order for rewrite systems, the exponential path order EPO*. Suppose a term rewrite system is compatible with EPO*, then the runtime complexity of this rewrite system is bounded from above by an exponential function. Furthermore, the class of function computed by a rewrite system compatible with EPO* equals the class of functions computable in exponential time on a Turing machine.
Categories
Term Rewriting, Complexity Analysis, Runtime Complexity Analysis, Path Orders, ICC, Predicative Recursion