[Back]

B. Gramlich, F. Schernhammer:
"Extending Context-Sensitivity in Term Rewriting";
Talk: 9th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2009), Brasilia (Brazil); 2009-06-28; in: "Prelim. Proc. 9th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2009), Brasilia, Brazil, June 28, 2009", M. Fernandez (ed.); (2009), 25 - 29.

Context-sensitive rewriting as pioneered by [Lucas 1995] has turned out to be a remarkably fruitful concept in many respects. Still, various examples and problems cannot be treated in a satisfactory way within this framework, because the underlying notion of context-sensitivity is too rigid and specialized. From a systematic point of view, it is only a very special case of a more general concept of context-sensitivity. In this contribution we will discuss more general versions of context-sensitivity, the relationships among them and the commonly used notion of context-sensitivity, as well as their feasibility from a computational point of view. In particular, we will present first steps towards an extended approach for context-sensitivity that is based on the notion of "forbidden patterns" which appears to be a reasonable compromise between expressive power and practical feasibility. The basic idea here is that a rewrite step should be forbidden if the redex to be contracted has a certain shape and appears in a certain context.

term rewriting, context-sensitivity, forbiden pattern

http://publik.tuwien.ac.at/files/PubDat_183426.pdf