License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2011.123
URN: urn:nbn:de:0030-drops-31127
URL: http://drops.dagstuhl.de/opus/volltexte/2011/3112/
 Go to the corresponding LIPIcs Volume Portal

### A Path Order for Rewrite Systems that Compute Exponential Time Functions

 pdf-format:

### 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.

### BibTeX - Entry

```@InProceedings{avanzini_et_al:LIPIcs:2011:3112,
author =	{Martin Avanzini and Naohi Eguchi and Georg Moser},
title =	{{A Path Order for Rewrite Systems that Compute Exponential Time Functions}},
booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
pages =	{123--138},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-30-9 },
ISSN =	{1868-8969},
year =	{2011},
volume =	{10},
editor =	{Manfred Schmidt-Schau{\ss}},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3112},
URN =		{urn:nbn:de:0030-drops-31127},
doi =		{http://dx.doi.org/10.4230/LIPIcs.RTA.2011.123},
annote =	{Keywords:  Runtime Complexity, Exponential Time Functions, Implicit Computational Complexity}
}
```

 Keywords: Runtime Complexity, Exponential Time Functions, Implicit Computational Complexity Seminar: 22nd International Conference on Rewriting Techniques and Applications (RTA'11) Issue Date: 2011 Date of publication: 26.04.2011

DROPS-Home | Fulltext Search | Imprint