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

Maja Hanne Kirkeby
, Robert Glück

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

5 Citations (Scopus)

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
Title of host publication	Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers : 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers
Editors	Maurizio Gabbrielli
Number of pages	17
Place of Publication	Cham
Publisher	Springer
Publication date	1 Apr 2020
Pages	243-259
ISBN (Print)	978-3-030-45259-9
ISBN (Electronic)	978-3-030-45260-5
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/Territory	Portugal
City	Porto
Period	08/10/2019 → 10/10/2019
Internet address	http://www.cs.unibo.it/projects/lopstr19/

Series	Lecture Notes in Computer Science
Number	12042
ISSN	0302-9743

Series	Theoretical Computer Science and General Issues
Number	12042

Keywords

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

Access to Document

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

Citation Styles

Kirkeby, M. H., & Glück, R. (2020). Semi-inversion of Conditional Constructor Term Rewriting Systems. In M. Gabbrielli (Ed.), Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers: 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers (pp. 243-259). Springer. https://doi.org/10.1007/978-3-030-45260-5_15

Kirkeby, Maja Hanne ; Glück, Robert. / Semi-inversion of Conditional Constructor Term Rewriting Systems. Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers: 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers. editor / Maurizio Gabbrielli. Cham : Springer, 2020. pp. 243-259 (Lecture Notes in Computer Science; No. 12042). (Theoretical Computer Science and General Issues; No. 12042).

@inproceedings{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.",

keywords = "Program transformation, Program inversion, Conditional term rewriting systems, Logic and functional programs",

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

isbn = "978-3-030-45259-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "12042",

pages = "243--259",

editor = "Maurizio Gabbrielli",

booktitle = "Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers",

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

}

Kirkeby, MH & Glück, R 2020, Semi-inversion of Conditional Constructor Term Rewriting Systems. in M Gabbrielli (ed.), Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers: 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers. Springer, Cham, Lecture Notes in Computer Science, no. 12042, Theoretical Computer Science and General Issues, no. 12042, pp. 243-259, 29th International Symposium Logic-Based Program Synthesis and Transformation, Porto, Portugal, 08/10/2019. https://doi.org/10.1007/978-3-030-45260-5_15

Semi-inversion of Conditional Constructor Term Rewriting Systems. / Kirkeby, Maja Hanne; Glück, Robert.
Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers: 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers. ed. / Maurizio Gabbrielli. Cham: Springer, 2020. p. 243-259 (Lecture Notes in Computer Science; No. 12042). (Theoretical Computer Science and General Issues; No. 12042).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

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.

KW - Program transformation

KW - Program inversion

KW - Conditional term rewriting systems

KW - Logic and functional programs

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

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

M3 - Article in proceedings

SN - 978-3-030-45259-9

T3 - Lecture Notes in Computer Science

SP - 243

EP - 259

BT - Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers

A2 - Gabbrielli, Maurizio

PB - Springer

CY - Cham

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

Y2 - 8 October 2019 through 10 October 2019

ER -

Kirkeby MH, Glück R. Semi-inversion of Conditional Constructor Term Rewriting Systems. In Gabbrielli M, editor, Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019, Revised Selected Papers: 29th International Symposium, LOPSTR 2019, Porto, Portugal, October 8–10, 2019, Revised Selected Papers. Cham: Springer. 2020. p. 243-259. (Lecture Notes in Computer Science; No. 12042). (Theoretical Computer Science and General Issues; No. 12042). doi: 10.1007/978-3-030-45260-5_15