Abstract
Productivity is the property that finite prefixes of an infinite constructor term can be computed using a given term rewrite system. Hitherto, productivity has only been considered for orthogonal systems, where non-determinism is not allowed. This paper presents techniques to also prove productivity of non-orthogonal term rewrite systems. For such systems, it is desired that one does not have to guess the reduction steps to perform, instead any outermost-fair reduction should compute an infinite constructor term in the limit. As a main result, it is shown that for possibly non-orthogonal term rewrite systems this kind of productivity can be concluded from context-sensitive termination.
| Original language | English |
|---|---|
| Title of host publication | Reduction Strategies in Rewriting and Programming (10th International Workshop, WRS 2011, Novi Sad, Serbia, May 29, 2011. Informal proceedings) |
| Editors | S. Escobar |
| Place of Publication | Valencia |
| Publisher | Universidad Politecnica de Valencia |
| Pages | 35-39 |
| Publication status | Published - 2011 |