An Event Structure Semantics for P/T Contextual Nets: Asymmetric Event Structures

Paolo Baldan - Andrea Corradini Dipartimento di Informatica University of Pisa Corso Italia, 40, 56125 Pisa Italy

Ugo Montanari SRI International Computer Science Laboratory 333 Ravenswood Ave. Menlo Park, CA 94025 USA

Abstract:

We propose an event based semantics for contextual nets, i.e. an extension of Place/Transition Petri nets where transitions can also have context conditions, modelling resources that can be read without being consumed. The result is a generalization of Winskel's work on safe nets: the event based semantics is given at categorical level via a chain of coreflections leading from the category WS-CN of weakly safe contextual nets to the category Dom of finitary prime algebraic domains.

A fundamental rôle is played by the notion of asymmetric event structures that generalize Winskel's prime event structures, following an idea similar to that of ``possible flow'' introduced by Pinna and Poignè. Asymmetric event structures have the usual causal relation of traditional prime event structures, but replace the symmetric conflict with a relation modelling asymmetric conflict or weak causality. Such relation allows one to represent the new kind of dependency between events arising in contextual nets, as well as the usual symmetric conflict. Moreover it is used in a non-trivial way in the definition of the ordering of configurations, which is different from the standard set-inclusion.