# IMFUFA Seminar: Program Inversion ved Maja Kirkeby (RUC/IMT)

Program inversion is an elementary program to program transformation and is a generalization of the function inversion known from Mathematics.
Onsdag
15
september
Start:kl. 14.00
Slut:kl. 16.00
Sted: Roskilde Universitet 27.1, lokale 1

Given a specification of the known input and output arguments of a program, a program inverter creates a new program where the known arguments are input, and the rest is output. There are three kinds of program inversions, namely full inversion, partial inversion and semi-inversion, where semi-inversion is the most general one. If p is a program with two inputs (x,y) and two outputs (u,v), then the three forms of inversion can be illustrated as follows.

p(x,y) = <u,v> == full inversion ==> p'(u,v) = <x,y>
p(x,y) = <u,v> == partial inversion ==> p'(x,u,v) = <y>
p(x,y) = <u,v> == semi inversion ==> p('x,v) = <u,y>

Full inversion swaps the entire input and output, partial inversion swaps parts of the input and the entire output, and semi-inversion allows parts of the input and output to be swapped. Important applications include the full inversion of lossless encoders, e.g., encode(data) = code into decode(code) = data, the partial inversion of symmetric encrypters, inverting, e.g., encrypt(key; data) = code into decrypt(key; code) = data, and the semiinversion of equation systems to isolate the unknown variables.

Program inversion algorithms are often tightly connected to a particular programming language, and instead, we use conditional constructor term rewriting systems; these systems model reversible, functional and declarative languages. In this talk, we present and discuss inverters developed for these rewrite systems.

## Tilmelding

Alle er velkomne, tilmelding er ikke nødvendig.

## Find vej

Find vej til Roskilde Universitet