Sound Structure-Preserving Transformation for Weakly-Left-Linear Deterministic Conditional Term Rewriting Systems

Ryota Nakayama
(Nagoya University)
Naoki Nishida
(Nagoya University)
Masahiko Sakai
(Nagoya University)

In this paper, we show that the SR transformation, a computationally equivalent transformation proposed by Serbanuta and Rosu, is a sound structure-preserving transformation for weakly-left-linear deterministic conditional term rewriting systems. More precisely, we show that every weakly-left-linear deterministic conditional term rewriting system can be converted to an equivalent weakly-left-linear and ultra-weakly-left-linear deterministic conditional term rewriting system and prove that the SR transformation is sound for weakly-left-linear and ultra-weakly-left-linear deterministic conditional term rewriting systems. Here, soundness for a conditional term rewriting system means that reduction of the transformed unconditional term rewriting system creates no undesired reduction sequence for the conditional system.

In Horatiu Cirstea and Santiago Escobar: Proceedings Third International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2016), Porto, Portugal, 23rd June 2016, Electronic Proceedings in Theoretical Computer Science 235, pp. 62–77.
Published: 1st January 2017.

ArXived at: http://dx.doi.org/10.4204/EPTCS.235.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org