Semi-inversion of Conditional Constructor Term Rewriting Systems

Maja Hanne Kirkeby, Robert Glück

Research output: Contribution to conferencePaperResearchpeer-review


Inversion is an important and useful program transformation and has been studied in various programming language paradigms. Semi-inversion is more general than just swapping the input and output of a program; instead, parts of the input and output can be freely swapped. In this paper, we present a polyvariant semi-inversion algorithm for conditional constructor term rewriting systems. These systems can model logic and functional languages, which have the advantage that semi-inversion, as well as partial and full inversion, can be studied across different programming paradigms. The semi-inverter makes use of local inversion and a simple but effective heuristic and is proven to be correct. A Prolog implementation is applied to several problems, including inversion of a simple encrypter and of a program inverter for a reversible language.
Original languageEnglish
Publication date1 Apr 2020
Publication statusPublished - 1 Apr 2020
Event29th International Symposium Logic-Based Program Synthesis and Transformation - Porto, Portugal
Duration: 8 Oct 201910 Oct 2019
Conference number: 29


Conference29th International Symposium Logic-Based Program Synthesis and Transformation
Internet address

Cite this