DROPS

Document

DOI: 10.4230/OASIcs.WPTE.2014.27

Inverse Unfold Problem and Its Heuristic Solving

Authors: Masanori Nagashima, Tomofumi Kato, Masahiko Sakai, and Naoki Nishida

Published in: OASIcs, Volume 40, First International Workshop on Rewriting Techniques for Program Transformations and Evaluation (2014)

Abstract

Unfold/fold transformations have been widely studied in various programming paradigms and are used in program transformations, theorem proving, and so on. This paper, by using an example, show that restoring an one-step unfolding is not easy, i.e., a challenging task, since some rules used by unfolding may be lost. We formalize this problem by regarding one-step program transformation as a relation. Next we discuss some issues on a specific framework, called pure-constructor systems, which constitute a subclass of conditional term rewriting systems. We show that the inverse of T preserves rewrite relations if T preserves rewrite relations and the signature. We propose a heuristic procedure to solve the problem, and show its successful examples. We improve the procedure, and show examples for which the improvement takes effect.

Cite as

Masanori Nagashima, Tomofumi Kato, Masahiko Sakai, and Naoki Nishida. Inverse Unfold Problem and Its Heuristic Solving. In First International Workshop on Rewriting Techniques for Program Transformations and Evaluation. Open Access Series in Informatics (OASIcs), Volume 40, pp. 27-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nagashima_et_al:OASIcs.WPTE.2014.27,
  author =	{Nagashima, Masanori and Kato, Tomofumi and Sakai, Masahiko and Nishida, Naoki},
  title =	{{Inverse Unfold Problem and Its Heuristic Solving}},
  booktitle =	{First International Workshop on Rewriting Techniques for Program Transformations and Evaluation},
  pages =	{27--38},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-70-5},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{40},
  editor =	{Schmidt-Schau{\ss}, Manfred and Sakai, Masahiko and Sabel, David and Chiba, Yuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WPTE.2014.27},
  URN =		{urn:nbn:de:0030-drops-45848},
  doi =		{10.4230/OASIcs.WPTE.2014.27},
  annote =	{Keywords: program transformation, unfolding, conditional term rewriting system}
}

Search Results

Documents authored by Nagashima, Masanori

Inverse Unfold Problem and Its Heuristic Solving

Abstract

Cite as

Thanks for your feedback!

Could not send message