cl-banner

A Path Order for Rewrite Systems that Compute Exponential Time Functions

Martin Avanzini, Naohi Eguchi, and Georg Moser

Proceedings of the 22nd International Conference on Rewriting Techniques and Applications (RTA 2011), Leibniz International Proceedings in Informatics 10, pp. 123 – 138, 2011.

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.

 

  PDF |    doi:10.4230/LIPIcs.RTA.2011.123  |  © Creative Commons License – NC – ND

BibTeX 

@inproceedings{MANEGM-RTA11,
author = "Martin Avanzini and Naohi Eguchi and Georg Moser",
title = "A Path Order for Rewrite Systems that Compute Exponential Time Functions",
booktitle = "Proceedings of the 22nd International Conference on Rewriting
Techniques and Applications",
series = "Leibniz International Proceedings in Informatics",
volume = 10,
pages = "123--138",
year = 2011
}
Nach oben scrollen