Abstract

Kennaway proved the remarkable result that every (almost) orthogonal term rewriting system admits a computable sequential normalizing reduction strategy. In this paper we present a computable sequential reduction strategy similar in scope, but simpler and more general. Our strategy can be thought of as an outermost-fair-like strategy that is allowed to be unfair to some redex of a term when contracting the redex is useless for the normalization of the term. Unlike the strategy of Kennaway, our strategy does not rely on syntactic restrictions that imply confluence. On the contrary, it can easily be applied to any term rewriting system, and we show that the class of term rewriting systems for which our strategy is normalizing properly includes all (almost) orthogonal systems. Our strategy is more versatile; in case of (almost) orthogonal term rewriting systems, it can be used to detect certain cases of non-termination. Our normalization proof is more accessible than Kennaway's. We also show that our sequential strategy sometimes succeeds where the parallel-outermost strategy fails.

BibTeX Entry

@article{AM-TCS96,
 author    = "Sergio Antoy and Aart Middeldorp",
 title     = "A Sequential Reduction Strategy",
 journal   = "Theoretical Computer Science",
 volume    = 165,
 number    = 1,
 pages     = "75--95",
 year      = 1996,
 doi       = "10.1016/0304-3975(96)00041-2"
}