Talks and Poster Presentations (with Proceedings-Entry):
B. Gramlich, F. Schernhammer:
"Extending Context-Sensitivity in Term Rewriting";
Talk: 9th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2009),
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.);
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
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.