[Back]


Talks and Poster Presentations (without Proceedings-Entry):

F. Schernhammer:
"Generalizing Context-Sensitivity in Term Rewriting";
Talk: 3rd Austria-Japan Summer Workshop on Term Rewriting, Obergurgl; 2010-08-01 - 2010-08-07.



English abstract:
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 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 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.

Currently, our work is focussing on the definition of criteria that
guarantee finiteness (i.e. termination) and completeness of rewriting
with forbidden patterns, where by completeness we mean the ability to
simulate certain unrestricted derivations (e.g., head-normalizing
ones) by restricted rewriting. In the work presented at WRS'09 some
criteria of this kind were presented. However, these were restricted
to certain classes of forbidden patterns and were not easy to check
automatically. We expect to generalize and improve upon these results
in the course of the next year and to present this progress at the
Austria Japan Workshop on Rewriting in 2010
(joint work with Bernhard Gramlich).


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_194742.pdf


Created from the Publication Database of the Vienna University of Technology.