Semi-inversion of Conditional Constructor Term Rewriting Systems

Maja Hanne Kirkeby, Robert Glück

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer 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.
OriginalsprogEngelsk
TitelLogic-Based Program Synthesis and Transformation : 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers
RedaktørerMaurizio Gabbrielli
UdgivelsesstedCham
ForlagSpringer
Publikationsdato1 apr. 2020
Sider243-259
ISBN (Trykt)978-3-030-45259-9
ISBN (Elektronisk)978-3-030-45260-5
DOI
StatusUdgivet - 1 apr. 2020
Begivenhed29th International Symposium Logic-Based Program Synthesis and Transformation - Porto, Portugal
Varighed: 8 okt. 201910 okt. 2019
Konferencens nummer: 29
http://www.cs.unibo.it/projects/lopstr19/

Konference

Konference29th International Symposium Logic-Based Program Synthesis and Transformation
Nummer29
LandPortugal
ByPorto
Periode08/10/201910/10/2019
Internetadresse
NavnLecture Notes in Computer Science
Nummer12042
ISSN0302-9743
NavnTheoretical Computer Science and General Issues
Nummer12042

Citer dette