  Termination of programs, i.e., the absence of infinite computations, ensures
the existence of normal forms for all initial expressions, thus providing an
essential ingredient for the definition of a normalization semantics for
functional programs. In lazy functional languages, though, infinite data
structures are often delivered as the outcome of computations. For instance,
the list of all prime numbers can be returned as a neverending stream of
numerical expressions or data structures. If such streams are allowed,
requiring termination is hopeless. In this setting, the notion of productivity
can be used to provide an account of computations with infinite data
structures, as it "captures the idea of computability, of progress of
infinite-list programs" (B.A. Sijtsma, On the Productivity of Recursive List
Definitions, ACM Transactions on Programming Languages and Systems
11(4):633-649, 1989). However, in the realm of Term Rewriting Systems, which
can be seen as (first-order, untyped, unconditional) functional programs,
termination of Context-Sensitive Rewriting (CSR) has been showed equivalent to
productivity of rewrite systems through appropriate transformations. In this
way, tools for proving termination of CSR can be used to prove productivity. In
term rewriting, CSR is the restriction of rewriting that arises when reductions
are allowed on selected arguments of function symbols only. In this paper we
show that well-known results about the computational power of CSR are useful to
better understand the existing connections between productivity of rewrite
systems and termination of CSR, and also to obtain more powerful techniques to
prove productivity of rewrite systems.
