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 higher-order 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 non-standard compilation methods relate to more standard techniques in the compilation of functional programming languages, namely continuation passing and defunctionalization. The interpretation of the lambda-calculus in a model of computation by interaction is related to a call-by-name CPS-translation followed by a defunctionalization procedure that takes into account control-flow information. I will describe the relation first for the linear lambda-calculus, then extend this to the simply-typed lambda-calculus and consider extensions, such as recursion.
- 15:30 – 16:30
-
Valeria Vignudelli (Università di Bologna)Invited talk: On the Discriminating Power of Higher-order Languages
We compare the discriminating power of higher-order sequential and concurrent languages (lambda-calculi, CCS-like calculi, Higher-Order pi-calculi), 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 first-order 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 higher-order constructs, concurrency and probabilistic systems.
(Joint work with Marco Bernardo and Davide Sangiorgi).
