The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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.2011.361
URN: urn:nbn:de:0030-drops-31350
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3135/
Go to the corresponding LIPIcs Volume Portal

Durand, Irène ; Sylvestre, Marc

Left-linear Bounded TRSs are Inverse Recognizability Preserving

pdf-format:
28.pdf (0.5 MB)

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 =		{10.4230/LIPIcs.RTA.2011.361},
  annote =	{Keywords: Term Rewriting, Preservation of Recognizability, Rewriting Strategies}
}

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

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