The complexity of normal form rewrite sequences for Associativity
| dc.creator | Niv, Michael | |
| dc.date | 1994-06-20 | |
| dc.date | 1994-06-20 | |
| dc.date.accessioned | 2026-07-07T08:58:36Z | |
| dc.date.available | 2026-07-07T08:58:36Z | |
| dc.description | The complexity of a particular term-rewrite system is considered: the rule of associativity (x*y)*z --> x*(y*z). Algorithms and exact calculations are given for the longest and shortest sequences of applications of --> that result in normal form (NF). The shortest NF sequence for a term x is always n-drm(x), where n is the number of occurrences of * in x and drm(x) is the depth of the rightmost leaf of x. The longest NF sequence for any term is of length n(n-1)/2. | |
| dc.description | 5 pages | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9406030 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9406030 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/147386 | |
| dc.subject | Computation and Language | |
| dc.title | The complexity of normal form rewrite sequences for Associativity | |
| dc.type | text |