Talks and Poster Presentations (with Proceedings-Entry):
K. Gmeiner, B. Gramlich, F. Schernhammer:
"On (Un)Soundness of Unravelings";
Talk: 21st International Conference on Rewriting Techniques and Applications,
Edinburgh;
2010-07-11
- 2010-07-13; in: "Proceedings of the 21st International Conference on Rewriting Techniques and Applications",
Chris Lynch (ed.);
LIPIcs - Leibniz International Proceedings in Informatics / Dagstuhl Publishing,
Volume 6, Dagstuhl
(2010),
ISBN: 978-3-939897-18-7;
119
- 134.
English 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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.RTA.2010.119
Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_194663.pdf
Created from the Publication Database of the Vienna University of Technology.