Séminaire, 25 septembre 2014
Programme
 10:30 – 12:00

Ugo Dal Lago (Università di Bologna, Italie)
Computational indistinguishability is one of the most central concepts in modern cryptography, and many other definitions (e.g. pseudorandomness, security of cryptographic schemes) can be formulated in terms of CI. We present the results of a study directed towards giving a direct and precise characterization of computational indistinguishability in an higherorder functional language for polynomial time computability, in which tools from implicit computational complexity and coinduction both play a central role. This is joint work with Alberto Cappai.
 14:00 – 15:00

Ulrich Schöpp (LMU, Munich)
In Game Semantics, the Geometry of Interaction and related approaches to programming language semantics, programs are modelled by interactive processes. Such interactive semantic models have been used in the design of new compilation methods, e.g. for hardware synthesis or for programming with sublinear space. This talk is about how such semantically motivated nonstandard compilation methods relate to more standard techniques in the compilation of functional programming languages, namely continuation passing and defunctionalization. The interpretation of the lambdacalculus in a model of computation by interaction is related to a callbyname CPStranslation followed by a defunctionalization procedure that takes into account controlflow information. I will describe the relation first for the linear lambdacalculus, then extend this to the simplytyped lambdacalculus and consider extensions, such as recursion.
 15:30 – 16:30

Valeria Vignudelli (Università di Bologna)Invited talk: On the Discriminating Power of Higherorder Languages
We compare the discriminating power of higherorder sequential and concurrent languages (lambdacalculi, CCSlike calculi, HigherOrder picalculi), possibly enriched with refusal or passivation operators. The comparison is carried out by defining a testing scenario where contexts of these languages are used to distinguish firstorder processes, which may be either ordinary nondeterministic processes or probabilistic processes.
The hierarchies of contextual/testing equivalences so obtained allow us both to compare different languages and to investigate the interplay between higherorder constructs, concurrency and probabilistic systems.
(Joint work with Marco Bernardo and Davide Sangiorgi).