License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.33
URN: urn:nbn:de:0030-drops-26436
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2643/
Go to the corresponding LIPIcs Volume Portal

Avanzini, Martin ; Moser, Georg

Closing the Gap Between Runtime Complexity and Polytime Computability

pdf-format:
10002.AvanziniMartin.2643.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{avanzini_et_al:LIPIcs:2010:2643,
  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},
  pages =	{33--48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2643},
  URN =		{urn:nbn:de:0030-drops-26436},
  doi =		{10.4230/LIPIcs.RTA.2010.33},
  annote =	{Keywords: Term rewriting, graph rewriting, complexity analysis, polytime computability}
}

Keywords: Term rewriting, graph rewriting, complexity analysis, polytime computability
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI