Aritmetica dei campi finiti e complessità polinomiale implicita (joint work with D.Canavese, E. Cesena, R. Ouchary e L. Roversi)

Marco Pedicini (RomaTre)
08/11/2013 - 11:00
Dipartimento di Matematica e Fisica: aula seminari 311, edificio C, Largo San Leonardo Murialdo 1, 00146 Roma.

We introduce a library of pure functional terms with the following features:

(i) any term can be typed in a type system which implicitly certifies it belongs
to the class of terms which evaluate in polynomial time;

(ii) they implement all the basic functions required to perform arithmetic on binary finite fields.

The type assignment system is Type Functional Assembly (TFA), an extension of Dual Light Affine Logic (DLAL).
The development of the whole library shows we can think of TFA as a domain specific language in which
the composition of variants of standard functional programming schemes drives a programmer to think of
implementations under non standard patterns.