2026-07-26T17:14:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3125 2024-03-06T10:33:52Z ddc:004 open_access

Program Inversion for Tail Recursive Functions Nishida, Naoki Vidal, German term rewriting program transformation termination 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Naoki Nishida and German Vidal 2011 Is Part Of LIPIcs, Volume 10, 22nd International Conference on Rewriting Techniques and Applications (RTA'11) (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2011.283 urn:nbn:de:0030-drops-31253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2011.283 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode