TR#:  LCL9406 
Class:  LCL 
Title:  THE COMPLEXITY OF NORMAL FORM REWRITE SEQUENCES FOR ASSOCIATIVITY. 
Authors:  M. Niv 
LCL9406.pdf  
Abstract: 
The complexity of a particular termrewrite system is considered: the rule of associativity (x \ast y) \ast z \rhd x \ast (y \ast z). Algorithms and exact calculations are given for the longest and shortest sequences of applications of \rhd that result in normal form (NF). The shortest NF sequence for a term x is always n  d_{\mbox{rm}}(x), where n is the number of occurrences of \ast in x and d_{\mbox{rm}}(x) is the depth of the rightmost leaf of x. The longest NF sequence for any term is of length n(n1)/2.

Copyright  The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information 
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1994/LCL/LCL9406), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the LCL technical reports of 1994
To the main CS technical reports page