- -

Reversible computation in term rewriting

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

Reversible computation in term rewriting

Show simple item record

Files in this item

dc.contributor.author Nishida, Naoki es_ES
dc.contributor.author Palacios, Adrián es_ES
dc.contributor.author Vidal, Germán es_ES
dc.date.accessioned 2019-06-07T20:02:43Z
dc.date.available 2019-06-07T20:02:43Z
dc.date.issued 2018 es_ES
dc.identifier.issn 2352-2208 es_ES
dc.identifier.uri http://hdl.handle.net/10251/121738
dc.description.abstract [EN] Essentially, in a reversible programming language, for each forward computation from state S to state S', there exists a constructive method to go backwards from state S' to state S. Besides its theoretical interest, reversible computation is a fundamental concept which is relevant in many different areas like cellular automata, bidirectional program transformation, or quantum computing, to name a few. In this work, we focus on term rewriting, a computation model that underlies most rule-based programming languages. In general, term rewriting is not reversible, even for injective functions; namely, given a rewrite step t(1) -> t(2), we do not always have a decidable method to get t(1) from t(2). Here, we introduce a conservative extension of term rewriting that becomes reversible. Furthermore, we also define two transformations, injectivization and inversion, to make a rewrite system reversible using standard term rewriting. We illustrate the usefulness of our transformations in the context of bidirectional program transformation. (C) 2017 Elsevier Inc. All rights reserved. es_ES
dc.description.sponsorship This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (MINECO) under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-R, by the Generalitat Valenciana under grant PROMETE0-II/2015/013 (SmartLogic), and by the COST Action IC1405 on Reversible Computation extending horizons of computing. Adrian Palacios was partially supported by the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formacian de doctores and Ayudas a la movilidad predoctoral para la realizacion de estancias breves en centros de I+D, MINECO (SEIDI), under FPI grants BES-2014-069749 and EEBB-I-16-11469. Part of this research was done while the second and third authors were visiting Nagoya University; they gratefully acknowledge their hospitality. es_ES
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation MINECO/TIN2013-44742-C4-1-R es_ES
dc.relation AEI/TIN2016-76843-C4-1-R es_ES
dc.relation GV/PROMETEOII/2015/013 es_ES
dc.relation EC/COST action IC1405 es_ES
dc.relation MINECO/BES-2014-069749 es_ES
dc.relation.ispartof Journal of Logical and Algebraic Methods in Programming es_ES
dc.rights Reconocimiento - No comercial - Sin obra derivada (by-nc-nd) es_ES
dc.subject Term rewriting es_ES
dc.subject Reversible computation es_ES
dc.subject Program transformation es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title Reversible computation in term rewriting es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1016/j.jlamp.2017.10.003 es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Nishida, N.; Palacios, A.; Vidal, G. (2018). Reversible computation in term rewriting. Journal of Logical and Algebraic Methods in Programming. 94:128-149. https://doi.org/10.1016/j.jlamp.2017.10.003 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://doi.org/10.1016/j.jlamp.2017.10.003 es_ES
dc.description.upvformatpinicio 128 es_ES
dc.description.upvformatpfin 149 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 94 es_ES
dc.relation.pasarela S\362583 es_ES
dc.contributor.funder European Commission es_ES
dc.contributor.funder Generalitat Valenciana es_ES
dc.contributor.funder Agencia Estatal de Investigación es_ES
dc.contributor.funder Ministerio de Economía y Empresa es_ES
dc.contributor.funder Ministerio de Economía, Industria y Competitividad es_ES


This item appears in the following Collection(s)

Show simple item record