Name
Abstract | ||
|---|---|---|
In previous papers, the authors studied normalization relative to desirable sets S of partial results, where it is shown that such sets must be stable. For example, the sets of normal forms, head-normal-forms, and weak head-normal-forms in the -calculus, are all stable. They showed that, for any stable S, S-needed reductions are S-normalizing. This paper continues the investigation into the theory of relative normalization. In particular, we prove existence of minimal normalizing reductions for regular stable sets of results. All the above mentioned sets are regular. We give a sufficient and necessary criterion for a normalizing reduction (w.r.t. a regular stable S) to be minimal. Finally, we establish a relationship between relative minimal and optimal reductions, revealing a conflict between minimality and optimality: for regular stable sets of results, a term need not possess a reduction that is minimal and optimal at the same time. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/3-540-62034-6_53 | FSTTCS |
Keywords | Field | DocType |
orthogonal expression reduction systems,minimal relative normalization,stable set,normal form | Discrete mathematics,Combinatorics,Lambda calculus,Normalization (statistics),Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-62034-6 | 2 | 0.38 |
References | Authors | |
23 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John R. W. Glauert | 1 | 145 | 12.14 |
| Zurab Khasidashvili | 2 | 307 | 25.40 |