Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Durand, Irène; Sylvestre, Marc http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-31350
URL:

;

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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3135},
  URN =		{urn:nbn:de:0030-drops-31350},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.RTA.2011.361},
  annote =	{Keywords: Term Rewriting, Preservation of Recognizability, Rewriting Strategies}
}

Keywords: Term Rewriting, Preservation of Recognizability, Rewriting Strategies
Seminar: 22nd International Conference on Rewriting Techniques and Applications (RTA'11)
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI