License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.119
URN: urn:nbn:de:0030-drops-26485
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2648/

Gmeiner, Karl ; Gramlich, Bernhard ; Schernhammer, Felix

On (Un)Soundness of Unravelings

pdf-format:
Dokument 1.pdf (185 KB)


Abstract

We revisit (un)soundness of transformations of conditional into unconditional rewrite systems. The focus here is on so-called unravelings, the most simple and natural kind of such transformations, for the class of normal conditional systems without extra variables. By a systematic and thorough study of existing counterexamples and of the potential sources of unsoundness we obtain several new positive and negative results. In particular, we prove the following new results: Confluence, non-erasingness and weak left-linearity (of a given conditional system) each guarantee soundness of the unraveled version w.r.t. the original one. The latter result substantially extends the only known sufficient criterion for soundness, namely left-linearity. Furthermore, by means of counterexamples we refute various other tempting conjectures about sufficient conditions for soundness.

BibTeX - Entry

@InProceedings{gmeiner_et_al:LIPIcs:2010:2648,
  author =	{Karl Gmeiner and Bernhard Gramlich and Felix Schernhammer},
  title =	{{On (Un)Soundness of Unravelings}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{119--134},
  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/2648},
  URN =		{urn:nbn:de:0030-drops-26485},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.RTA.2010.119},
  annote =	{Keywords: Conditional rewriting, transformation into unconditional systems, unsoundness, unraveling}
}

Keywords: Conditional rewriting, transformation into unconditional systems, unsoundness, unraveling
Seminar: 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 Published by LZI