Technical Report LCL9406

TR#:LCL9406
Class:LCL
Title: THE COMPLEXITY OF NORMAL FORM REWRITE SEQUENCES FOR ASSOCIATIVITY.
Authors: M. Niv
PDFLCL9406.pdf
Abstract:

The complexity of a particular term-rewrite 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(n-1)/2.

CopyrightThe 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/cgi-bin/tr-info.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

Computer science department, Technion
admin