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

### Left-linear Bounded TRSs are Inverse Recognizability Preserving

 pdf-format:

### Abstract

Bounded rewriting for linear term rewriting systems has been defined in (I. Durand, G. Sénizergues, M. Sylvestre. Termination of linear bounded term rewriting systems. Proceedings of the 21st International Conference on Rewriting Techniques and Applications) as a restriction of the usual notion of rewriting. We extend here this notion to the whole class of left-linear term rewriting systems, and we show that bounded rewriting is effectively inverse-recognizability preserving. The bounded class (BO) is, by definition, the set of left-linear systems for which every derivation can be replaced by a bottom-up derivation. The class BO contains (strictly) several classes of systems which were already known to be inverse-recognizability preserving: the left-linear growing systems, and the inverse right-linear finite-path overlapping systems.

### BibTeX - Entry

```@InProceedings{durand_et_al:LIPIcs:2011:3135,
author =	{Ir{\`e}ne Durand and Marc Sylvestre},
title =	{{Left-linear Bounded TRSs are Inverse Recognizability Preserving}},
booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
pages =	{361--376},
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},