Semi-inversion of Conditional Constructor Term Rewriting Systems

Maja Hanne Kirkeby; Robert Glück

doi:10.1007/978-3-030-45260-5_15

Semi-inversion of Conditional Constructor Term Rewriting Systems

Research output: Contribution to conference › Paper › Research › peer-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 language	English
Publication date	1 Apr 2020
DOIs	https://doi.org/10.1007/978-3-030-45260-5_15
Publication status	Published - 1 Apr 2020
Event	29th International Symposium Logic-Based Program Synthesis and Transformation - Porto, Portugal Duration: 8 Oct 2019 → 10 Oct 2019 Conference number: 29 http://www.cs.unibo.it/projects/lopstr19/

Conference

Conference	29th International Symposium Logic-Based Program Synthesis and Transformation
Number	29
Country	Portugal
City	Porto
Period	08/10/2019 → 10/10/2019
Internet address	http://www.cs.unibo.it/projects/lopstr19/

Link to document

10.1007/978-3-030-45260-5_15Licence: Unspecified

Cite this

@conference{1885192480a54cedb4543397ae30c2ee,

title = "Semi-inversion of Conditional Constructor Term Rewriting Systems",

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.",

author = "Kirkeby, {Maja Hanne} and Robert Gl{\"u}ck",

year = "2020",

month = apr,

day = "1",

doi = "10.1007/978-3-030-45260-5_15",

language = "English",

note = "29th International Symposium Logic-Based Program Synthesis and Transformation, LOPSTR 2019 ; Conference date: 08-10-2019 Through 10-10-2019",

url = "http://www.cs.unibo.it/projects/lopstr19/",

}

TY - CONF

T1 - Semi-inversion of Conditional Constructor Term Rewriting Systems

AU - Kirkeby, Maja Hanne

AU - Glück, Robert

N1 - Conference code: 29

PY - 2020/4/1

Y1 - 2020/4/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-45260-5_15

DO - 10.1007/978-3-030-45260-5_15

M3 - Paper

T2 - 29th International Symposium Logic-Based Program Synthesis and Transformation

Y2 - 8 October 2019 through 10 October 2019

ER -