Extending Context-Sensitivity in Term Rewriting

Details Extending Context-Sensitivity in Term Rewriting Extending Context-Sensitivity in Term Rewriting

2010-01-25

arxiv.org/abs/1001.4437v1

EPTCS 15, 2010, pp. 56-68

Computer Science

Logic in Computer Science

Scientific paper

10.4204/EPTCS.15.5

We propose a generalized version of context-sensitivity in term rewriting based on the notion of "forbidden patterns". The basic idea is that a rewrite step should be forbidden if the redex to be contracted has a certain shape and appears in a certain context. This shape and context is expressed through forbidden patterns. In particular we analyze the relationships among this novel approach and the commonly used notion of context-sensitivity in term rewriting, as well as the feasibility of rewriting with forbidden patterns from a computational point of view. The latter feasibility is characterized by demanding that restricting a rewrite relation yields an improved termination behaviour while still being powerful enough to compute meaningful results. Sufficient criteria for both kinds of properties in certain classes of rewrite systems with forbidden patterns are presented.

Affiliated with

Also associated with

No associations

Rating

Extending Context-Sensitivity in Term Rewriting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extending Context-Sensitivity in Term Rewriting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extending Context-Sensitivity in Term Rewriting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-131069