tr-announce Januar 2002

tr-announce@lists.rwth-aachen.de

1 Teilnehmer
2 Diskussionen

[tr-announce] AIB: Kolloquium Programmiersprachen und Grundlagen der Programmierung

von Volker Stolz

The following technical report is available from http://aib.informatik.rwth-aachen.de: Klaus Indermark and Thomas Noll (eds.) Kolloquium Programmiersprachen und Grundlagen der Programmierung 2001-11 Abstract: This report contains the proceedings of the Colloquium on "Programmiersprachen und Grundlagen der Programmierung", which was held between October 7 and 11, 2001, at Rurberg, Germany. -- Volker Stolz * stolz(a)i2.informatik.rwth-aachen.de

22 Jahre, 2 Monate

[tr-announce] AIB: Transformation Techniques for Context-Sensitive Rewrite Systems

von Volker Stolz

The following technical report is available from http://aib.informatik.rwth-aachen.de: Jürgen Giesl, Aart Middledorp Transformation Techniques for Context-Sensitive Rewrite Systems 2002-02 Abstract: Context-sensitive rewriting is a term rewriting strategy used to model non-strict (lazy) evaluation in functional programming. The goal of this paper is the study and development of techniques to analyse the termination behavior of context-sensitive rewrite systems. For that purpose, several methods have been proposed in the literature which transform context-sensitive rewrite systems into ordinary rewrite systems such that termination of the transformed ordinary system implies termination of the original context-sensitive system. In this way, the huge variety of existing techniques for termination analysis of ordinary rewriting can be used for context-sensitive rewriting, too. We analyse the existing transformation techniques for proving termination of context-sensitive rewriting and we suggest two new transformations. Our first method is simple, sound, and more powerful than the previously proposed transformations. However, it is not complete, i.e., there are terminating context-sensi\-tive rewrite systems that are transformed into non-terminating term rewrite systems. The second method that we present in this paper is both sound and complete. All these observations also hold for rewriting modulo associativity and commutativity. Our completeness result can be interpreted as stating that one no longer needs any special techniques for the termination analysis of context-sensitive rewriting. Regards, Volker Stolz -- Volker Stolz * stolz(a)i2.informatik.rwth-aachen.de

22 Jahre, 3 Monate

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce Januar 2002