DROPS

Document

DOI: 10.4230/LIPIcs.FSCD.2016.28

Reversible Term Rewriting

Authors: Naoki Nishida, Adrián Palacios, and Germán Vidal

Published in: LIPIcs, Volume 52, 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)

Abstract

Essentially, in a reversible programming language, for each forward computation step from state S to state S', there exists a constructive and deterministic 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 paper, 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 t1 -> t2, we do not always have a decidable and deterministic method to get t1 from t2. Here, we introduce a conservative extension of term rewriting that becomes reversible. Furthermore, we also define a transformation to make a rewrite system reversible using standard term rewriting.

Cite as

Naoki Nishida, Adrián Palacios, and Germán Vidal. Reversible Term Rewriting. In 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 52, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{nishida_et_al:LIPIcs.FSCD.2016.28,
  author =	{Nishida, Naoki and Palacios, Adri\'{a}n and Vidal, Germ\'{a}n},
  title =	{{Reversible Term Rewriting}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Kesner, Delia and Pientka, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2016.28},
  URN =		{urn:nbn:de:0030-drops-59841},
  doi =		{10.4230/LIPIcs.FSCD.2016.28},
  annote =	{Keywords: term rewriting, reversible computation, program transformation}
}

Document

DOI: 10.4230/OASIcs.WPTE.2015.19

Towards Modelling Actor-Based Concurrency in Term Rewriting

Authors: Adrián Palacios and Germán Vidal

Published in: OASIcs, Volume 46, 2nd International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2015)

Abstract

In this work, we introduce a scheme for modelling actor systems within sequential term rewriting. In our proposal, a TRS consists of the union of three components: the functional part (which is specific of a system), a set of rules for reducing concurrent actions, and a set of rules for defining a particular scheduling policy. A key ingredient of our approach is that concurrent systems are modelled by terms in which concurrent actions can never occur inside user-defined function calls. This assumption greatly simplifies the definition of the semantics for concurrent actions, since no term traversal will be needed. We prove that these systems are well defined in the sense that concurrent actions can always be reduced. Our approach can be used as a basis for modelling actor-based concurrent programs, which can then be analyzed using existing techniques for term rewrite systems.

Cite as

Adrián Palacios and Germán Vidal. Towards Modelling Actor-Based Concurrency in Term Rewriting. In 2nd International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2015). Open Access Series in Informatics (OASIcs), Volume 46, pp. 19-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{palacios_et_al:OASIcs.WPTE.2015.19,
  author =	{Palacios, Adri\'{a}n and Vidal, Germ\'{a}n},
  title =	{{Towards Modelling Actor-Based Concurrency in Term Rewriting}},
  booktitle =	{2nd International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2015)},
  pages =	{19--29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-94-1},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{46},
  editor =	{Chiba, Yuki and Escobar, Santiago and Nishida, Naoki and Sabel, David and Schmidt-Schau{\ss}, Manfred},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WPTE.2015.19},
  URN =		{urn:nbn:de:0030-drops-51792},
  doi =		{10.4230/OASIcs.WPTE.2015.19},
  annote =	{Keywords: concurrency, actor model, rewriting}
}

Search Results

Documents authored by Palacios, Adrián

Reversible Term Rewriting

Abstract

Cite as

Towards Modelling Actor-Based Concurrency in Term Rewriting

Abstract

Cite as

Thanks for your feedback!

Could not send message