Talks and Poster Presentations (with Proceedings-Entry):
B. Gramlich, S. Lucas:
"Generalizing Newman's Lemma for Left-Linear Rewrite Systems";
Talk: 17th International Conference on Rewriting Techniques and Applications (RTA 2006),
- 2006-08-14; in: "Term Rewriting and Applications, 17th International Conference, RTA 2006, Seattle, Washington, USA, August 12-14, 2006, Proceedings, LNCS 4098",
F. Pfenning (ed.);
Confluence criteria for non-terminating rewrite systems are known to be rare and notoriously difficult to obtain. Here we prove a new result in this direction. Our main result is a generalized version of Newman's Lemma for left-linear term rewriting systems that does not need a full termination assumption. We discuss its relationships to previous confluence criteria, its restrictions, examples of application as well as open problems. The whole approach is developed in the (more general) framework of context-sensitive rewriting which thus turns out to be useful also for ordinary (context-free) rewriting.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.