Publications in Scientific Journals:
F. Schernhammer, B. Gramlich:
"Termination of Lazy Rewriting Revisited";
Electronic Notes in Theoretical Computer Science (ENTCS),
204
(2008),
35
- 51.
English abstract:
Lazy rewriting is a proper restriction of term rewriting that dynamically restricts the reduction of certain arguments of functions
in order to obtain termination. In contrast to context-sensitive rewriting, reductions at such argument positions are not completely forbidden but delayed.
Based on the observation that the only existing (non-trivial) approach to prove termination of such lazy rewrite systems is flawed, we develop a modified approach for transforming lazy rewrite systems into context-sensitive ones that is sound and complete with respect to termination. First experimental results with this transformation based technique are encouraging.
Keywords:
Lazy rewriting, termination, context-sensitivity.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.entcs.2008.03.052
Electronic version of the publication:
http://publik.tuwien.ac.at/files/pub-inf_4988.pdf
Created from the Publication Database of the Vienna University of Technology.