Computer Science – Computational Complexity
Scientific paper
2010-01-29
Computer Science
Computational Complexity
Submitted to RTA 2010
Scientific paper
Recently, many techniques have been introduced that allow the (automated) classification of the runtime complexity of term rewrite systems (TRSs for short). In earlier work, the authors have shown that for confluent TRSs, innermost polynomial runtime complexity induces polytime computability of the functions defined. In this paper, we generalise the above result to full rewriting. Following our previous work, 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 non-deterministic polytime-computation based on runtime complexity analysis of rewrite systems.
Avanzini Martin
Moser Georg
No associations
LandOfFree
Efficient Implementation of Rewriting Revisited Technical Report does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Implementation of Rewriting Revisited Technical Report, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Implementation of Rewriting Revisited Technical Report will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-676816