2026-08-10T14:16:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2643 2024-03-06T10:33:28Z ddc:004 open_access

Closing the Gap Between Runtime Complexity and Polytime Computability Avanzini, Martin Moser, Georg Term rewriting graph rewriting complexity analysis polytime computability In earlier work, we have shown that for confluent TRSs, innermost polynomial runtime complexity induces polytime computability of the functions defined. In this paper, we generalise this result to full rewriting, for that we 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 (TM for short). We show that the runtime complexity of the TRS and the runtime complexity of the TM is polynomially related. Our result strengthens the evidence that the complexity of a rewrite system is truthfully represented through the length of derivations. Moreover our result allows the classification of nondeterministic polytime-computation based on runtime complexity analysis of rewrite systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Avanzini and Georg Moser 2010 Is Part Of LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2010.33 urn:nbn:de:0030-drops-26436 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.33 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode