Domínguez, Jesús and Fernández, Maribel - From nominal to higher-order rewriting and back again

lmcs:1610 - Logical Methods in Computer Science, December 14, 2015, Volume 11, Issue 4
From nominal to higher-order rewriting and back again

Authors: Domínguez, Jesús and Fernández, Maribel

We present a translation function from nominal rewriting systems (NRSs) to combinatory reduction systems (CRSs), transforming closed nominal rules and ground nominal terms to CRSs rules and terms, respectively, while preserving the rewriting relation. We also provide a reduction-preserving translation in the other direction, from CRSs to NRSs, improving over a previously defined translation. These tools, together with existing translations between CRSs and other higher-order rewriting formalisms, open up the path for a transfer of results between higher-order and nominal rewriting. In particular, techniques and properties of the rewriting relation, such as termination, can be exported from one formalism to the other.


Source : oai:arXiv.org:1509.05318
DOI : 10.2168/LMCS-11(4:9)2015
Volume: Volume 11, Issue 4
Published on: December 14, 2015
Submitted on: November 5, 2014
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 70 times.
This article's PDF has been downloaded 31 times.