cl-banner

Closing the Gap Between Runtime Complexity and Polytime Complexity

Martin Avanzini and Georg Moser

Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA 2010), Leibniz International Proceedings in Informatics 6, pp. 33 – 48, 2010.

Abstract

In earlier work, we have shown that for confluent term rewrite systems, innermost polynomial runtime complexity induces polytime computability of the functions defined. In this paper, we generalise this result to full rewriting. For that, we again exploit graph rewriting. We give a new proof of the adequacy of graph rewriting for full rewriting that allows for a precise control of the resources copied. In sum we completely describe an implementation of rewriting on a Turing machine. We show that the runtime complexity with respect to rewrite systems is polynomially related to the runtime complexity on a Turing machine. Our result strengthens the evidence that the complexity of a rewrite system is truthfully represented through the length of deriva-tions. Moreover our result allows the classification of deterministic as well as nondeterministic polytime-computation based on runtime complexity analysis of rewrite systems.

 

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

BibTeX 

@inproceedings{MAGM-RTA10,
author = "Martin Avanzini and Georg Moser",
title = "Closing the Gap Between Runtime Complexity and Polytime Computability",
booktitle = "Proceedings of the 21st International Conference on
Rewriting Techniques and Applications",
series = "Leibniz International Proceedings in Informatics",
volume = 6,
pages = "33--48",
year = 2010
}
Nach oben scrollen