Generalizing Context-Sensitivity in Term Rewriting


Context-sensitive rewriting as pioneered by S. Lucas since 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 our contribution we will discuss such a more general approach to
context-sensitivity 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. We present the current state of the art in our research
of rewriting with forbidden patterns concerning termination and
completeness.