Computer Science – Logic in Computer Science
Scientific paper
2010-05-31
LMCS 6 (2:5) 2010
Computer Science
Logic in Computer Science
Scientific paper
10.2168/LMCS-6(2:5)2010
We define two transformations from term rewriting systems (TRSs) to context-sensitive TRSs in such a way that termination of the target system implies outermost termination of the original system. In the transformation based on 'context extension', each outermost rewrite step is modeled by exactly one step in the transformed system. This transformation turns out to be complete for the class of left-linear TRSs. The second transformation is called `dynamic labeling' and results in smaller sized context-sensitive TRSs. Here each modeled step is adjoined with a small number of auxiliary steps. As a result state-of-the-art termination methods for context-sensitive rewriting become available for proving termination of outermost rewriting. Both transformations have been implemented in Jambox, making it the most successful tool in the category of outermost rewriting of the last edition of the annual termination competition.
Endrullis Joerg
Hendriks Dimitri
No associations
LandOfFree
Transforming Outermost into Context-Sensitive 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 Transforming Outermost into Context-Sensitive Rewriting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transforming Outermost into Context-Sensitive Rewriting will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-627663