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

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	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
Redaktører	Maurizio Gabbrielli
Antal sider	17
Udgivelsessted	Cham
Forlag	Springer
Publikationsdato	1 apr. 2020
Sider	243-259
ISBN (Trykt)	978-3-030-45259-9
ISBN (Elektronisk)	978-3-030-45260-5
DOI	https://doi.org/10.1007/978-3-030-45260-5_15
Status	Udgivet - 1 apr. 2020
Begivenhed	29th International Symposium Logic-Based Program Synthesis and Transformation - Porto, Portugal Varighed: 8 okt. 2019 → 10 okt. 2019 Konferencens nummer: 29 http://www.cs.unibo.it/projects/lopstr19/

Konference

Konference	29th International Symposium Logic-Based Program Synthesis and Transformation
Nummer	29
Land/Område	Portugal
By	Porto
Periode	08/10/2019 → 10/10/2019
Internetadresse	http://www.cs.unibo.it/projects/lopstr19/

Navn	Lecture Notes in Computer Science
Nummer	12042
ISSN	0302-9743

Navn	Theoretical Computer Science and General Issues
Nummer	12042

Link til dokument

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

Citer dette

Kirkeby, M. H., & Glück, R. (2020). Semi-inversion of Conditional Constructor Term Rewriting Systems. I M. Gabbrielli (red.), 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 (s. 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. red. / Maurizio Gabbrielli. Cham : Springer, 2020. s. 243-259 (Lecture Notes in Computer Science; Nr. 12042). (Theoretical Computer Science and General Issues; Nr. 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. i M Gabbrielli (red.), 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, nr. 12042, Theoretical Computer Science and General Issues, nr. 12042, s. 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. red. / Maurizio Gabbrielli. Cham: Springer, 2020. s. 243-259 (Lecture Notes in Computer Science; Nr. 12042). (Theoretical Computer Science and General Issues; Nr. 12042).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › 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. I Gabbrielli M, red., 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. s. 243-259. (Lecture Notes in Computer Science; Nr. 12042). (Theoretical Computer Science and General Issues; Nr. 12042). doi: 10.1007/978-3-030-45260-5_15