Semi-inversion of Conditional Constructor Term Rewriting Systems

Maja Hanne Kirkeby, Robert Glück

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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
Title of host publicationLogic-Based Program Synthesis and Transformation : 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers
EditorsMaurizio Gabbrielli
Place of PublicationCham
PublisherSpringer
Publication date1 Apr 2020
Pages243-259
ISBN (Print)978-3-030-45259-9
ISBN (Electronic)978-3-030-45260-5
DOIs
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
http://www.cs.unibo.it/projects/lopstr19/

Conference

Conference29th International Symposium Logic-Based Program Synthesis and Transformation
Number29
Country/TerritoryPortugal
CityPorto
Period08/10/201910/10/2019
Internet address
SeriesLecture Notes in Computer Science
Number12042
ISSN0302-9743
SeriesTheoretical Computer Science and General Issues
Number12042

Keywords

  • Program transformation
  • Program inversion
  • Conditional term rewriting systems
  • Logic and functional programs

Cite this