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 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.
|
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/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