License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2011.283
URN: urn:nbn:de:0030-drops-31253
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3125/
Go to the corresponding LIPIcs Volume Portal

Nishida, Naoki ; Vidal, German

Program Inversion for Tail Recursive Functions

pdf-format:
18.pdf (0.6 MB)

Abstract

Program inversion is a fundamental problem that has been addressed in
many different programming settings and applications. In the context
of term rewriting, several methods already exist for computing the
inverse of an injective function. These methods, however, usually
return non-terminating inverted functions when the considered function
is tail recursive. In this paper, we propose a direct and intuitive
approach to the inversion of tail recursive functions. Our new
technique is able to produce good results even without the use of an
additional post-processing of determinization or completion. Moreover,
when combined with a traditional approach to program inversion, it
constitutes a promising approach to define a general method for
program inversion. Our experimental results confirm that the new
technique compares well with previous approaches.

BibTeX - Entry

@InProceedings{nishida_et_al:LIPIcs:2011:3125,
  author =	{Naoki Nishida and German Vidal},
  title =	{{Program Inversion for Tail Recursive Functions}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{283--298},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9 },
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Manfred Schmidt-Schau{\ss}},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3125},
  URN =		{urn:nbn:de:0030-drops-31253},
  doi =		{10.4230/LIPIcs.RTA.2011.283},
  annote =	{Keywords: term rewriting, program transformation, termination}
}

Keywords: term rewriting, program transformation, termination
Collection: 22nd International Conference on Rewriting Techniques and Applications (RTA'11)
Issue Date: 2011
Date of publication: 26.04.2011

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