Valeria Vignudelli (Università di Bologna), 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).