License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WPTE.2014.27
URN: urn:nbn:de:0030-drops-45848
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4584/
Go to the corresponding OASIcs Volume Portal

Nagashima, Masanori ; Kato, Tomofumi ; Sakai, Masahiko ; Nishida, Naoki

Inverse Unfold Problem and Its Heuristic Solving

pdf-format:
p027-04-nagashima.pdf (0.5 MB)

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.

BibTeX - Entry

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

Keywords: program transformation, unfolding, conditional term rewriting system
Collection: First International Workshop on Rewriting Techniques for Program Transformations and Evaluation
Issue Date: 2014
Date of publication: 13.07.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI