La variazione rispetto alla comunicazione precedente riguarda l'orario. Il seminario si terrà dunque alle 10.30.

Venerdì 21 maggio

Ore 10.30 in Aula Verra, Facoltà di Lettere e Filosofia - Università Roma Tre, via Ostiense 234

Seminario:

-- Damiano Mazza - Measuring the Expressiveness of Rewriting Systems through Event Structures

Abstract

We develop a methodology for studying and comparing the expressiveness of computational models which are based on rewriting. We consider a class of rewriting systems, which we call normal, admitting a natural interpretation in terms of event structures; this is done by building up on work of Mazurkiewicz, Nielsen, Plotkin, Winskel, Melliès, and Mimram. Then, we introduce the notion of bisimilar embedding of event structures, which allows us to say when a computational system is "at least as expressive" as another one, as soon as these two are described in terms of event structures. Finally, we prove a few separation results for normal rewriting systems based on this notion, and we give an application of these to interaction nets and their non-deterministic variants, including Ehrhard and Regnier's differential interaction nets.

Gruppo di Logica e Geometria della Cognizione -- http://logica.uniroma3.it