[Back]

B. Gramlich, F. Schernhammer:
"Extending Context-Sensitivity in Term Rewriting";
Report No. E1852-2009-02, 2009; 22 pages.

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.

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