Unique normal forms in term rewriting systems with repeated variables
Paul T. K. Chew · 1981
A term rewriting system is a finite set of axiom schemata of the form [email protected]@@@B where A and B are terms that contain variables. An important question for such systems is whether normal forms are unique (i.e. each term has at most one normal form). For schemata without repeated variables (i.e. no variable is repeated on the left side of an axiom schema), O'Donnell [O'D] has given sufficient conditions for the confluence property (Church-Rosser property), a stronger property than unique normal forms. Klop [Klo] has shown that the confluence property does not necessarily hold in these systems when repeated variables are allowed. This paper shows that normal forms are unique in such systems despite the lack of the confluence property.