Lazy productivity via termination

作者：Endrullis Jorg; Hendriks Dimitri^*

来源：Theoretical Computer Science, 2011, 412(28): 3203-3225.

DOI：10.1016/j.tcs.2011.03.024

• Term rewriting
• Productivity
• Termination
• Strong sequentiality
• Lazy evaluation
• Context-sensitive rewriting
• Matrix interpretations

We present a procedure for transforming strongly sequential constructor-based term rewriting systems (TRSs) into context-sensitive TRSs in such a way that productivity of the input system is equivalent to termination of the output system. Thereby automated termination provers become available for proving productivity. A TRS is called productive if all its finite ground terms are constructor normalizing, and all 'inductive constructor paths' through the resulting (possibly non-wellfounded) constructor normal form are finite. To our knowledge, this is the first complete transformation from productivity to termination.
The transformation proceeds in two steps: (i) The strongly sequential TRS is converted into a shallow TRS, where patterns do not have nested constructors. (ii) The shallow TRS is transformed into a context-sensitive TRS, where rewriting below constructors and in arguments not 'consumed from' is disallowed.
Furthermore, we show how lazy evaluation can be encoded by strong sequentiality, thus extending our transformation to, e.g., Haskell programs.
Finally, we present a simple, but fruitful extension of matrix interpretations to make them applicable for proving termination of context-sensitive TRSs.

• 出版日期2011-6-20