# Operational Representation of Dependencies in Context-Dependent Event Structures

G. Michele Pinna

► To cite this version:

G. Michele Pinna. Operational Representation of Dependencies in Context-Dependent Event Structures. 22th International Conference on Coordination Languages and Models (COORDINATION), Jun 2020, Valletta, Malta. pp.320-338, 10.1007/978-3-030-50029-0_20. http-03273985

HAL Id: hal-03273985

https://inria.hal.science/hal-03273985

Submitted on 29 Jun 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Operational representation of dependencies in Context-Dependent Event Structures

G. Michele Pinna

Dipartimento di Matematica e Informatica, Università di Cagliari, Cagliari, Italy

**Abstract.** The execution of an event in a complex and distributed system where the dependencies vary during the evolution of the system can be represented in many ways, and one of them is to use Context-Dependent Event structures. Many kinds of event structures are related to various kind of Petri nets. The aim of this paper is to find the appropriate kind of Petri net that can be used to give an operational flavour to the dependencies represented in a Context/Dependent Event structure.

**Keywords:** Petri Nets, Event Structures, Operational Semantics, Contextual Nets

## 1 Introduction

Since the introduction of the notion of Event structure ([21] and [28]) the close relationship between this notion and suitable nets has been investigated. The ingredients of an event structure are, beside a set of events, a number of relations used to express which events can be part of a configuration (the snapshot of a concurrent system), modeling a consistency predicate, and how events can be added to reach another configuration, modeling the dependencies among the (sets of) events. On the nets side we have transitions, modeling the activities, and places, modeling resources the activities may need, consume or produces. These ingredients, together with some constraints on how places and transitions are related (via flow, inhibitor or read arcs satisfying suitable properties), can give also a more *operational* description of a concurrent and distributed system. Indeed the relationship between event structures and nets is grounded on the observation that also in (suitable) Petri nets the relations among events are representable, as it has been done in [14] for what concern the partial order and [21] for the partial order and conflict.

Since then several notions of event structures have been proposed. We recall just few of them: the classical *prime* event structures [28] where the dependency between events, called *causality*, is modeled by a partial order and the consistency is described by a symmetric *conflict* relation. Then *flow* event structures [6] drop the requirement that the dependency should be a partial order on the whole set of events, *bundle* event structures [17] represent OR-causality by allowing each event to be caused by a unique member of a bundle of events (and this constraint may be relaxed). *Asymmetric* event structures [4], via notion of weak causality,
model asymmetric conflicts, whereas *Inhibitor* event structures [3] are able to faithfully capture the dependencies among events which arise in the presence of read and inhibitor arcs in safe nets. In [5] a notion of event structures where the causality relation may be circular is investigated, and in [1] the notion of dynamic causality is considered. Finally, we mention the quite general approach presented in [13], where there is a unique relation, akin to a *deduction relation*. To each of the mentioned event structures a particular class of nets is related. Prime event structures have a correspondence in *occurrence nets*, flow event structures have flow nets whereas *unravel nets* [7] are related to bundle event structures. Continuing we have that asymmetric and inhibitor event structures have a correspondence with *contextual nets* [4, 3], and event structures with circular causality with *lending nets* [5], finally to those with dynamic causality we have *inhibitor unravel nets* [9] and to the configuration structures presented in [13] we have the notion of *1-occurrence nets*. Most of the approaches relating nets with event structures are based on the equation "event = transition", even if many of the events represent the same *high level* activity. The idea that some of the transitions may be somehow identified as they represent the same activity is the one pursued in many works aiming at reducing the size of the net, like *merged processes* ([16]), *trellis processes* ([11]), *merging relation* approach ([8]) or *spread nets* ([12] and [25]), but these approaches are mostly unrelated with event structure of any kind.

In this paper we pursue the usual problem: given an event structure, find a
net which may correspond to it. To find the kind of net that can be associated to
context-dependent event structures ([23] and [24]) we first observe that in these
event structures each event may happen in many different and often unrelated
contexts, hence the same event cannot have (almost) the same past as it happens
in many approaches. The second observation is that dependencies among tran-
sitions (events) in nets may be represented in different ways. Consider the case
of a Petri net with inhibitor arcs ([15]) where the precondition of the transition
e' inhibits the transition e (the net N). The latter to happens needs that the
transition e' happens first, and the observation testifies that the activity e needs
that e' has already happened, though resources are not exchanged between e'
and e. On the contrary, in the net N without inhibitor arcs the token (resource)
produced by e' is mandatory for e to happen.

<figure><img src="image_2.png" /></figure>

Both nets represent the same dependency: e' should happen before e. Following
these two observations we argue that each of the context that are *allowing* an
event to happen can be modeled with *inhibitor* and/or *read* arcs. It should be
stressed that these kind of arcs have been introduced for different purposes, but
never for nets which are meant to describe the behaviour of another one. The approach we pursue here is originated in the one we adopted for dynamic event structures in [9], though here also the *classical* dependencies among events (those called causal dependencies) are boiled down to the same machinery. Indeed we argued that the proper net corresponding to these kind of event structure are meant to give an *operational* representation of what *denotationally* can be characterized as a single event but operationally are rather different transitions. The approach is a conservative one: the dependencies represented in different kind on nets can be represented also in this approach and similarly to suitably characterized nets it is possible to associate the corresponding context-dependent event structure. It should be stressed that the conflicts between events in causal nets are explicitly represented and cannot be inferred otherwise.

*Organization of the paper.* In the next section we recall the notions of contextual nets, occurrence net and prime event structure and also ho the two latter notions are related. In Section 3 we recall the notion of context-dependent event structure and in Section 4 we introduce the notion of *causal* net and we show also how occurrence nets can be seen as causal nets. We also give a direct translation from prime event structures to causal net and vice versa. In Section 5 we discuss how to associate a causal net to a context-dependent event structure and vice versa, showing that the notion of causal net is adequate. Some conclusions end the paper.

## 2 Preliminaries

We denote with $\mathbb{N}$ the set of natural numbers. Let $A$ be a set, a *multiset* of $A$ is a function $m: A \to \mathbb{N}$. The set of multisets of $A$ is denoted by $\mu A$. We assume the usual operations on multisets such as union $+$ and difference $-$*. We write $m \subseteq m'$ if $m(a) \le m'(a)$ for all $a \in A$. For $m \in \mu A$, we denote with $[[m]]$ the multiset defined as $[[m]](a) = 1$ if $m(a) > 0$ and $[[m]](a) = 0$ otherwise. When a multiset $m$ of $A$ is a set, i.e. $m = [[m]]$, we write $a \in m$ to denote that $m(a) \ne 0$, and often confuse the multiset $m$ with the set $\{a \in A | m(a) \ne 0\}$ or a subset $X \subseteq A$ with the multiset $X(a) = 1$ if $a \in A$ and $X(a) = 0$ otherwise. Furthermore we use the standard set operations like $\cap$, $\cup$ or $\setminus$.

Given a set $A$ and a relation $< \subseteq A \times A$, we say that $<$ is an *irreflexive* partial order whenever it is irreflexive and transitive. We shall write $\le$ for the reflexive closure of an irreflexive partial order $<$. Given an irreflexive relation $\prec \subseteq A \times A$, with $\prec^+$ we denote its transitive closure.

Given a function $f: A \to B$, $dom(f) = \{a \in A \mid \exists b \in B. f(a) = b\}$ is the domain of $f$, and $codom(f) = \{b \in B \mid \exists a \in A. f(a) = b\}$ is the codomain of $f$.

Given a set $A$, a sequence of elements in $A$ is a partial mapping $\rho: \mathbb{N} \to A$ such that, given any $n \in \mathbb{N}$, if $\rho(n)$ is defined and equal to $a \in A$ then $\forall i \le n$ also $\rho(i)$ is defined. A sequence is finite if $dom(\rho)$ is finite, and the length of a sequence $\rho$, denoted with $len(\rho)$, is the cardinality of $dom(\rho)$. A sequence $\rho$ is often written as $a_1a_2\cdots$ where $a_i = \rho(i)$. With $\bar{\rho}$ we denote the codomain of $\rho$.
Requiring that a sequence $\rho$ has distinct elements accounts to stipulate that $\rho$ is injective on $dom(\rho)$.

## 2.1 Contextual Petri nets

We review the notion of labeled Petri net with contextual arcs along with some auxiliary notions ([20] and [3]). We recall that a *net* is the 4-tuple $N = \langle S, T, F, I, R, \mathfrak{m}, \ell \rangle$ where $S$ is a set of *places* (usually depicted with circles) and $T$ is a set of *transitions* (usually depicted as squares) and $S \cap T = \emptyset$, $F \subseteq (S \times T) \cup (T \times S)$ is the *flow relation* and $\mathfrak{m} \in \mu S$ is called the *initial marking*. We assume to have a set $\mathcal{L}$ of labels.

**Definition 1.** A contextual Petri net is the tuple $N = \langle S, T, F, I, R, \mathfrak{m}, \ell \rangle$, where $\langle S, T, F, \mathfrak{m} \rangle$ is a net, $I \subseteq S \times T$ are the inhibitor arcs, $R \subseteq S \times T$ are the read arcs, and $\ell: T \to \mathcal{L}$ is the labeling mapping, and $\ell$ is a total function.

Inhibitor arcs depicted as lines with a circle on one end, and read arcs as plain lines. We sometimes omit the $\ell$ mapping when $\mathcal{L}$ is $T$ and $\ell$ is the identity. We will often call a contextual Petri net as Petri net or simply net.

Given a net $N = \langle S, T, F, I, R, \mathfrak{m} \rangle$ and $x \in S \cup T$, we define the following (multi)sets: $\bullet x = \{y \mid (y, x) \in F\}$ and $x^\bullet = \{y \mid (x, y) \in F\}$. If $x \in S$ then $\bullet x \in \mu T$ and $x^\bullet \in \mu T$; analogously, if $x \in T$ then $\bullet x \in \mu S$ and $x^\bullet \in \mu S$. Given a transition $t$, with $\circ t$ we denote the (multi)set $\{s \mid (s, t) \in I\}$ and with $\underline{t}$ the (multi)set $\{s \mid (s, t) \in \mathcal{R}\}$.

A transitions $t \in T$ is enabled at a marking $m \in \mu S$, denoted by $m[t]$, whenever $\bullet t + \underline{t} \subseteq m$ and $\forall s \in [\circ t]$. $m(s) = 0$. Observe that no token must be present in a place connected to a transition with an inhibitor arc. A transition $t$ enabled at a marking $m$ can fire and its firing produces the marking $m' = m - \bullet t + \underline{t}$. The firing of $t$ at a marking $m$ is denoted by $m[t]m'$. We assume that each transition $t$ of a net $N$ is such that $\bullet t \neq \emptyset$, meaning that no transition may fire *spontaneously*. Given a generic marking $m$ (not necessarily the initial one), the *firing sequence* (shortened as *fs*) of $N = \langle S, T, F, I, R, \mathfrak{m} \rangle$ starting at $m$ is defined as:

- $m$ is a firing sequence (of length 0), and

- if $m[t_1]m_1 \cdots m_{n-1}[t_n]m_n$ is a firing sequence and $m_n[t]m'$, then also $m[t_1]m_1 \cdots m_{n-1}[t_n]m_n[t]m'$ is a firing sequence.

The set of firing sequences of a net $N$ starting at a marking $m$ is denoted by $\mathcal{R}_m^N$ and it is ranged over by $\sigma$. Given a fs $\sigma = m[t_1]\sigma'[t_n]m_n$, we denote with start($\sigma$) the marking $m$ and with lead($\sigma$) the marking $m_n$. tail($\sigma$) denotes the fs $\sigma'[t_n]m_n$, provided that $\sigma$ is not of length 0, otherwise it is not defined. Given a net $N$, a marking $m$ is reachable iff there exists a fs $\sigma \in \mathcal{R}_m^N$ such that lead($\sigma$) is $m$. The set of reachable markings of $N$ is $M_N = \bigcup_{\sigma \in \mathcal{R}_m^N} lead(\sigma)$. Given a fs $\sigma = m[t_1]m_1 \cdots m_{n-1}[t_n]m'$, we write $X_\sigma = \sum_{i=1}^n \{t_i\}$ for the multiset of transitions associated to fs. We call $X_\sigma$ a state of the net and write $\text{St}(N) = \{X_\sigma \in \mu T \mid \sigma \in \mathcal{R}_m^N\}$ for the set of states of the net $N$. The configurations of a
net are the sets of labels of the executed transitions. Hence $Conf_{net}(N)$, is the set $\{\ell(X) | X \in St(N)\}$.

**Example 1.** The following net is a simple contextual Petri net. At the initial marking $t_2$ and $t_3$ are enabled whereas $t_1$ is not. After the execution of $t_2$ no other transition is enabled. After the firing of $t_3$ the transition $t_1$ is enabled, as no token is present in the place $s_2$ and a token is present in the place $s_6$, the former being connected to transition $t_1$ with an inhibitor arc and the latter being connected to transition $t_1$ with a read arc.

<figure><img src="image_3.png" /></figure>

The following definitions characterize nets from a *semantical* point of view.

**Definition 2.** A net $N = (S, T, F, I, R, \mathfrak{m}, \ell)$ is said to be safe if each marking $\mathfrak{m} \in \mathcal{M}_N$ is such that $\mathfrak{m} = [\mathfrak{m}]$.

In this paper we will consider safe nets, where each place contains at most one token. The following definitions outline nets with respect to states and configurations.

**Definition 3.** A net $N = (S, T, F, I, R, \mathfrak{m}, \ell)$ is said to be a single execution net if each state $X \in St(N)$ is such that $X = [X]$.

In a single execution net a transition $t$ in a firing sequence may be fired just once, as the net in Example 1. In [26] and [13] these nets (without inhibitor and read arcs) are called *1-occurrence net*.

**Definition 4.** A net $N = (S, T, F, I, R, \mathfrak{m}, \ell)$ is said to be an unfolding if each configuration $C \in Conf_{net}(N)$ is such that $C = [C]$.

Clearly each unfolding is also a single execution one, but the vice versa does not hold. When the labeling of the net is an injective mapping we have that to each state a configuration corresponds and vice versa.

**Remark 1.** In literature *unfolding* is often used to denote not only a net with suitable characteristic (among them the fact that each transition is fired just once in each execution), but also how this net is related to another one (the one to be unfolded). Here we use it to stress that each configuration is a set.

The following definition characterizes when two transitions never happen together in any execution (conflicting transitions).
**Definition 5.** Let $N = \langle S, T, F, I, R, \mathfrak{m}, \ell \rangle$ be a net and let $t, t' \in T$ such that $\forall X \in \mathrm{St}(N)$ it holds that $\{t, t'\} \not\subseteq [X]$. Then $N$ is conflict saturated with respect to $t, t'$ if $\bullet t \cap \bullet t' \neq \emptyset$.

Each net can be transformed into an equivalent one conflict saturated.

**Proposition 1.** Let $N = \langle S, T, F, I, R, \mathfrak{m}, \ell \rangle$ be a net and let $t, t' \in T$ such that $\forall X \in \mathrm{St}(N)$ it holds that $\{t, t'\} \not\subseteq [X]$, then the net $N^\# = \langle S \cup \{s_{t,t'}\}, T, F \cup \{(s_{t,t'}, t), (s_{t,t'}, t')\}, I, R, \mathfrak{m} \cup \{s_{t,t'}\}, \ell \rangle$ is conflict saturated with respect to $t, t'$ and $\mathrm{St}(N) = \mathrm{St}(N^\#)$.

Iterating this we can always construct a net which is conflict saturated with
respect to all the possible conflicting transitions.

**2.2 Occurrence nets and prime event structure**

We recall the notion of *occurrence net*, and as it has no inhibitor or read arc
nor a labeling, we omit *I*, *R* and *ℓ* in the following, assuming that *I* = *∅* = *R*
and *ℓ* being the identity on transitions. Given a net *N* = *⟨S, T, F, m⟩*, we write
*<N* for transitive closure of *F*. We say *N* is *acyclic* if *≤*<sub>*N*</sub> is a partial order. For
occurrence nets, we adopt the usual convention: places and transitions are called
as *conditions* and *events*, and use *B* and *E* for the sets of conditions and events.
We may confuse conditions with places and events with transitions. The initial
marking is denoted with *c*.

**Definition 6.** An occurrence net (on) *O* = ⟨*B*, *E*, *F*, *c*⟩ is an acyclic, safe net satisfying the following restrictions:

- $\forall b \in B$. $\bullet b$ is either empty or a singleton, and $\forall b \in c$. $\bullet b = \emptyset$,

- $\forall b \in B$. $\exists b' \in c$ such that $b' \leq_O b$,

- for all $e \in E$ the set $\lfloor e \rfloor = \{e' \in E \mid e' \leq_O e\}$ is finite, and

- # is an *irreflexive and symmetric relation defined as follows:*

- $e \#_0 e'$ iff $e, e' \in E, e \neq e'$ and $e \cap e' \neq \emptyset$,

- $x \# x'$ iff $\exists y, y' \in E$ such that $y \#_0 y'$ and $y \leq_O x$ and $y' \leq_O x'$.

The intuition behind occurrence nets is the following: each condition *b* represents the occurrence of a token, which is produced by the *unique* event in $\bullet b$, unless *b* belongs to the initial marking, and it is used by only one transition (hence if *e*, *e'* ∈ *b*\*, then *e* $\#$ *e'*). On an occurrence net *O* it is natural to define a notion of *causality* among elements of the net: we say that *x* is *causally dependent* on *y* iff *y* $\leq_O$ *x*. Occurrence nets are often the result of the *unfolding* of a (safe) net. In this perspective an occurrence net is meant to describe precisely the non-sequential semantics of a net, and each reachable marking of the occurrence net corresponds to a reachable marking in the net to be unfolded. Here we focus purely on occurrence nets and not on the nets they are the unfolding of.

**Proposition 2.** Let $O = \langle B, E, F, c \rangle$ be an occurrence net. Then $O$ is a single execution net and it is an unfolding.
Occurrence nets are relevant as they are tightly related to *prime event structures*, which we briefly recall here ([28]).

**Definition 7.** A prime event structure (PES) is a triple $P = (E, <, \#)$, where

- $E$ is a countable set of events,

- $\langle < \subseteq E \times E \rangle$ is an *irreflexive partial order called the causality relation, such that* $\forall e \in E$. $\{e' \in E \mid e' < e\}$ is *finite, and*

- $\# \subseteq E \times E$ is a conflict relation, which is *irreflexive, symmetric and hereditary relation with respect to $<$: if $e \# e' < e''$ then $e \# e''$ for all $e, e', e'' \in E$.

Given an event $e \in E$, $\lfloor e \rfloor$ denotes the set $\{e' \in E \mid e' \le e\}$. A subset of events $X \subseteq E$ is left-closed if $\forall e \in X$. $\lfloor e \rfloor \subseteq X$. Given a subset $X \subseteq E$ of events, $X$ is conflict free iff for all $e, e' \in X$ it holds that $e \ne e'$ $\Rightarrow \neg(e \# e')$, and we denote it with $CF(X)$. Given $X \subseteq E$ such that $CF(X)$ and $Y \subseteq X$, then also $CF(Y)$.

**Definition 8.** Let $P = (E, <, \#)$ be a PES. Then $X \subseteq E$ is a configuration if $CF(X)$ and $\forall e \in X$. $\lfloor e \rfloor \subseteq X$. The set of configurations of the PES $P$ is denoted by $\text{Conf}_{\text{PES}}(P)$.

Configurations are definable also in occurrence nets.

**Definition 9.** Let $O = (B, E, F, c)$ be an on and $X \subseteq E$ be a subset of events. Then $X$ is a configuration of $O$ whenever $CF(X)$ and $\forall e \in X$. $\lfloor e \rfloor \subseteq X$. The set of configurations of the on $O$ is denoted by $\text{Conf}_{\text{on}}(O)$.

Given an on $O = (B, E, F, c)$ and a state $X \in \text{St}(O)$, it is easy to see that it is conflict free, i.e. $\forall e, e' \in X$. $e \ne e'$ $\Rightarrow \neg(e \# e')$, and left closed, i.e. $\forall e \in X$. $\{e' \in E \mid e' \le_O e\} \subseteq X$.

**Proposition 3.** Let $O = (B, E, F, c)$ be an occurrence net and $X \in \text{St}(O)$. Then $X \in \text{Conf}_{\text{on}}(O)$.

Occurrence nets and prime event structures are connected as follows ([28]).

**Proposition 4.** Let $O = (B, E, F, c)$ be an on, and define $\mathcal{P}(O)$ as the triple $(E, <_C, \#)$ where $>_C$ is the *irreflexive and transitive relation obtained by F restricting to E × E and # is the irreflexive and symmetric relation associated to O*. Then $\mathcal{P}(O)$ is a PES, and $\text{Conf}_{\text{on}}(O) = \text{Conf}_{\text{PES}}(\mathcal{P}(O))$.

Also the vice versa is possible, namely given a prime event structure one can associate to it an occurrence net. The construction is indeed quite standard (see [28, 5] among many others).

**Definition 10.** Let $P = (E, \le, \#)$ be a PES. Define $\mathcal{E}(P)$ as the net $(B, E, F, c)$ where

- $B = \{(*, e) \mid e \in E\} \cup \{(e, *) \mid e \in E\} \cup \{(e, e', <) \mid e < e'\} \cup \{(\{e, e'\}, \#) \mid e \# e'\}$,

- $F = \{(e, b) \mid b = (e, *)\} \cup \{(e, b) \mid b = (e, e', <)\} \cup \{(b, e) \mid b = (*, e)\} \cup \{(b, e) \mid b = (e', e, <)\} \cup \{(b, e) \mid b = (Z, \#) \land e \in Z\}$, and
$$-c = \{(*, e) \mid e \in E\} \cup \{(\{e, e'\}, #) \mid e \neq e'\}.$$

**Proposition 5.** Let $P = (E, \leq, #)$ be a PES. Then $\mathcal{E}(P) = \langle B, E, F, c \rangle$ as defined in Definition 10 is an occurrence net.

In essence an occurrence net is fully characterized by the partial order relation and the *saturated* conflict relation. This observation, together with the fact that an immediate conflict in a safe net is represented by a common place in the preset of the conflicting events, suggests that conflicts may be modeled directly, which is the meaning of the following proposition and that will be handy in rest of the paper.

**Proposition 6.** Let $O = \langle B, E, F, c \rangle$ be an on and let # be the associated conflict relation. Then $O^# = \langle B \cup B^#, E, F \cup F^#, c \cup B^# \rangle$ where $B^# = \{\{e, e'\} \mid e \neq e'\}$ and $F^# = \{(A, e) \mid A \in B^# \wedge e \in A\}$, is an on such that $\text{Conf}_{\text{on}}(O) = \text{Conf}_{\text{on}}(C^#)$.

## 3 Context-Dependent Event Structure

We recall the notion of *Context-Dependent* event structure introduced in [23] and further studied in [24]. The idea is that the happening of an event depends on a set of modifiers (the *context*) and on a set of *real* dependencies, which are activated by the set of modifiers.

**Definition 11.** A context-dependent event structure (CDES) is a triple $E = (E, #, \gg)$ where

- $E$ is a set of events,

- $\# \subseteq E \times E$ is an *irreflexive and symmetric relation*, called conflict relation, and

- $\gg \subseteq 2^A \times E$, where $A \subseteq 2_{\text{fin}}^E \times 2_{\text{fin}}^E$, is a relation, called the context-dependency relation (CD-relation), which is such that for each $Z \gg e$ it holds that

* $Z \neq \emptyset$,

* for each $(X, Y) \in Z$ it holds that $\text{CF}(X)$ and $\text{CF}(Y)$, and

* for each $(X, Y), (X', Y') \in Z$ if $X = X'$ then $Y = Y'$.

The CD-relation models, for each event, which are the possible contexts in which the event may happen (the first component of each pair) and for each context which are the events that have to be occurred (the second component). We stipulate that dependencies and contexts are formed by non conflicting events. We recall the notion of enabling of an event. We have to determine, for each $Z \gg e$, which of the contexts $X_i$ should be considered. To do so we define the *context* associated to each entry of the CD-relation. Given $Z \gg e$, where $Z = \{(X_1, Y_1), \dots, (X_n, Y_n)\}$, with $\text{CXT}(Z)$ we denote the set of events $\bigcup_{i=1}^{|Z|} X_i$, and this is the one regarding $Z \gg e$.
**Definition 12.** Let $E = (E, \# , \gg)$ be a CDES and $C \subseteq E$ be a subset of events.
Then the event $e \notin C$ is enabled at $C$, denoted with $C[e]$, if for each $Z \gg e$, with
$Z = \{(X_1, Y_1), \dots, (X_n, Y_n)\}$, there is a pair $(X_i, Y_i) \in Z$ such that $\text{CXT}(Z) \cap C =$
$X_i$ and $Y_i \subseteq C$.

Observe that requiring the non emptiness of the set Z in Z $\gg$ e guarantees that
an event e may be enabled at some subset of events.

**Definition 13.** Let $E = (E, \# , \gg)$ be a CDES. Let $C$ be a subset of $E$. We say that $C$ is a configuration of the CDES $E$ iff there exists a sequence of distinct events $\rho = e_1 e_2 \cdots$ over $E$ such that

$$
- \bar{\rho} = C,
$$

- $\bar{\rho}$ is conflict-free, and

$$
- \forall 1 \le i \le \text{len}(\rho). \bar{p}_{i-1}[e_i].
$$

With $\text{Conf}_{\text{CDES}}(E)$ we denote the set of configurations of the CDES $E$.

We illustrate this kind of event structure with some examples, mainly taken from
[23] and [24].

*Example 2.* Consider three events *a*, *b* and *c*. All the events are singularly enabled but *a* and *b* are in conflict unless *c* has not happened (we will see later that this are called *resolvable conflicts*). Hence for the event *a* we stipulate

$$
\{(\emptyset, \emptyset), (\{c\}, \emptyset), (\{b\}, \{c\})\} \gg a
$$

that should be interpreted as follows: if the context is $\emptyset$ or $\{c\}$ then $a$ is enabled
without any further condition (the $Y$ are the empty set), if the context is $\{b\}$ then
also $\{c\}$ should be present. The set $\text{CXT}(\{(\emptyset, \emptyset), (\{c\}, \emptyset), (\{b\}, \{c\})\})$ is $\{b, c\}$.
Similarly, for the event $b$ we stipulate

$$
\{(\emptyset, \emptyset), (\{c\}, \emptyset), (\{a\}, \{c\})\} \gg b
$$

which is justified as above and finally for the event c we stipulate

$$
\{(\emptyset, \emptyset), (\{a\}, \emptyset), (\{b\}, \emptyset)\} \gg c
$$

namely any context allows to add the event.

*Example 3.* Consider three events *a*, *b* and *c*, and assume that *c* depends on *a*
unless the event *b* has occurred, and in this case this dependency is removed.
Thus there is a classic causality between *a* and *c*, but it can dropped if *b* occurs.
Clearly *a* and *b* are always enabled. The CD-relation is {((0, 0))} ≫ a, {((0, 0))} ≫ b
and {((0, {a}), ({b}, 0))} ≫ c.

*Example 4.* Consider three events *a*, *b* and *c*, and assume that *c* depends on *a*
just when the event *b* has occurred, and in this case this dependency is added,
otherwise it may happen without. Thus classic causality relation between *a* and
*c* is added if *b* occurs. Again *a* and *b* are always enabled. The CD-relation is
{((0, 0))} ≫ a, {((0, 0))} ≫ b and {((0, 0), ({b}, {a}))} ≫ c.
These examples should clarify how the CD-relation is used and also that each
event may be *implemented* by a different pair (X, Y) of modifiers and depen-
dencies.

In [23] and [24] we have shown that many event structures can be seen as a
CDES, and this is obtained taking the configurations of an event structure and
from these synthesizing the conflict and the ≫ relations. The CDES obtained in
this way have the same set of configurations of the event structure one started
with, and furthermore for each event e there is just one entry Z ≫ e.

**Definition 14.** Let $E = (E, \# , \gg)$ be a CDES. We say that $E$ is simple if $\forall e \in E$ there is just one entry $Z \gg e$.

**Proposition 7.** Let $E = (E, \# , \gg)$ be a CDES. Then there exists a simple CDES $E' = (E, \#', \gg')$ such that $\text{Conf}_{\text{CDES}}(E) = \text{Conf}_{\text{CDES}}(E')$.

# 4 Causal nets

We introduce a notion that will play the same role of occurrence net when related to context-dependent event structure.

Given a contextual Petri net $N = (S, T, F, I, R, \mathfrak{m}, \ell)$, we can associate to it a relation on transitions, denoted with $\prec_N$ and defined as $t \prec_N t'$ when $\bullet t \cap \ell t' \neq \emptyset$ or $t' \cap \ell t \neq \emptyset$, with the aim of establishing the dependencies among transitions related by inhibitor or read arcs. Similarly we can introduce a conflict relation among transitions, which is a semantic one. For this is enough to stipulate that two transitions $t, t' \in T$ are in conflict, denoted with $t \#_N t'$ if $\forall X \in \text{St}(N)$. $\{t, t'\} \not\subseteq [X]$. With the aid of these relations we can introduce the notion of causal net.

**Definition 15.** Let $U = (S, T, F, I, R, \mathfrak{m}, \ell)$ be a labeled Petri net over the set of label L. Then $U$ is a causal net (cn net) if the following further conditions are satisfied:

1. $\prec_U \cap (T \times T) = \emptyset, \forall t \in T. \bullet t \cap \ell t = \emptyset \text{ and } t' \cap \ell t = \emptyset$,

2. $\forall t \in T. \forall s \in \ell t. |\ell(s^\bullet)| = 1,$

3. $\forall t, t' \in T, t \prec_U t' \Rightarrow t' \not\prec_U t,$

4. $\forall t \in T \text{ the set } \ell t \cup \ell t' \text{ is finite,}$

5. $\forall t, t' \in T. t \#_U t' \Rightarrow \bullet t \cap \ell t' \neq \emptyset,$

6. $\forall X \in \text{St}(U) \prec_U^* X$ is a partial order on X, and

7. $\forall C \in \text{Conf}_{\text{cn}}(U). C = [C]$

The first requirement implies that $\forall t, t' \in T$ we have that $t' \cap \bullet t = \emptyset$, hence in
this kind of net the dependencies do not arise from the flow relation, furthermore
inhibitor and read arcs do not interfere with the flow relation. The second condi-
tion implies that if a token in a place inhibits the happening of a transition, then
all the transitions removing this token have the same label, the third is meant to
avoid cycles between transitions arising from inhibitor and read arcs, the fourth
one implies that for each transition $t$ the set $\{t' \in T \mid t' \prec_U t\}$ is finite, the fifth
one stipulates that two conflicting transitions (which never appear together in any execution of the net) are conflicting as they consume the same token from a place. Finally the last two conditions guarantee that the transitions in each execution can be totally ordered with respect the dependency relation associated to the net and that two transitions with the same label do not happen in the same computation. In particular the last condition implies that a causal net is also an unfolding.

It should be clear that the conditions posed on a causal net are meant to mimic some of the conditions posed on an occurrence net or on similar one, like for instance unravel nets ([22, 7] or [9]) or flow nets ([6]), and they should assure that it is comprehensible what a computation in such a net can be looking at labels, as the main intuition is that for the same activity (label) there may be several incarnations.

*Example 5.* The following one is a causal net:

<figure><img src="image_4.png" /></figure>

All the conditions of Definition 15 are fulfilled. The two transitions bearing the same label ($t_2$ and $t_3$) are conflicting ones, namely they never appear together in any computation though the activity realized by these two transitions (c) appears in all maximal computations.

The first observation we make on causal nets is that they are good candidates to be seen as a semantic net, namely a net meant to represent the behaviour of a system properly modeling dependencies and conflicts of any kind.

**Proposition 8.** Let $U = \langle S, T, F, I, R, m, \ell \rangle$ be a causal net. Then $U$ is an unfolding.

To give further evidence that this notion could be the appropriate one, we show that each occurrence net can be turned into a causal one, thus this is a conservative extension of this notion. The idea behind the construction is simple: to each event of the occurrence net a transition in the causal net is associated, the places in the preset of all transitions are initially marked and they are not in the postset of any other transition. The dependencies between events are modeled using inhibitor arcs. All the conflicts are modeled like in a conflict saturated net (with suitable marked places).

**Proposition 9.** Let $O = \langle B, E, F, c \rangle$ be an occurrence net. The net $O(O) = \langle S, E, F', I, \emptyset, m, \ell \rangle$ where

$$ - S = \{(*, e) \mid e \in E\} \cup \{(e, *) \mid e \in E\} \cup \{{e, e'} \mid e \neq e'\}, $$
$$- F' = \{(s, e) \mid s = (*, e)\} \cup \{(s, e) \mid e \in s\} \cup \{(e, s) \mid s = (e, *)\},$$

$$- I = \{(s, e) \mid s = (*, e') \wedge e' <_C e\},$$

$$- \mathbf{m}: S \to \mathbb{N} \text{ is such that } \mathbf{m}(s) = 0 \text{ if } s = (e, *) \text{ and } \mathbf{m}(s) = 1 \text{ otherwise, and}$$

$$- \ell \text{ is the identity,}$$

is a causal net over the set of label E, and $\text{Conf}_{\text{on}}(O) = \text{Conf}_{\text{cn}}(O(O))$.

Below we depict a simple occurrence net (on the left) and the associated causal one.

<figure><img src="image_5.png" /></figure>

**Proposition 10.** Let $O$ be an occurrence net and $O(O)$ be the associated causal net. Then $O(O)$ is conflict saturated.

In the causal net the dependencies are much more complicated to understand with respect to an occurrence net. However the Proposition 9, together with the connection among PES and on (Definition 10 and Proposition 5), suggests that a relation between PES and cn can be established. Here the intuition is to use the same construction hinted in Proposition 9.

**Definition 16.** Let $\mathbb{P} = (E, <, \#)$ be a PES. Define $\mathcal{A}(\mathbb{P})$ as the causal Petri net $(S, E, F, I, \emptyset, \mathbf{m}, \ell)$ where

$$- S = \{(*, e) \mid e \in E\} \cup \{(e, *) \mid e \in E\} \cup \{(\{e, e'\}, \#) \mid e \neq e'\},$$

$$- F = \{(e, s) \mid s = (e, *)\} \cup \{(s, e) \mid s = (*, e) \lor (s = (W, \#) \wedge e \in W)\},$$

$$- I = \{(s, e) \mid s = (*, e') \wedge e' < e\},$$

$$- \mathbf{m} = \{(*, e) \mid e \in E\} \cup \{(\{e, e'\}, \#) \mid e \neq e'\}, \text{ and}$$

$$- \ell \text{ is the identity.}$$

**Proposition 11.** Let $\mathbb{P}$ be a PES, and $\mathcal{A}(\mathbb{P})$ be the associated Petri net. Then $\mathcal{A}(\mathbb{P})$ is a causal net and $\text{Conf}_{\text{PES}}(\mathbb{P}) = \text{Conf}_{\text{cn}}(\mathcal{A}(\mathbb{P}))$.

**Proposition 12.** Let $\mathbb{P}$ be a PES, and $\mathcal{A}(\mathbb{P})$ be the associated causal net. Then $\mathcal{A}(\mathbb{P})$ is conflict saturated.

The vice versa is a bit more tricky as we have to require that the dependency relation $\prec$ and the conflict relation have a particular shape.
**Definition 17.** Let $U = \langle S, T, F, I, R, m, \ell \rangle$ be a causal net. $U$ is said to be an occurrence causal net whenever $R = \emptyset$, $\prec_U^*$ is a partial order over $T$, and if $t \#_U t' \prec_U^* t''$ then $t \#_U t''$.

The above definition simply guarantees that the dependencies give a partial order and that the conflict relation is inherited along the reflexive and transitive closure of the dependency relation.

**Proposition 13.** Let $\mathbf{P}$ be a PES, and $\mathcal{A}(\mathbf{P})$ be the associated Petri net. Then $\mathcal{A}(\mathbf{P})$ is an occurrence causal net.

Finally we show that also the vice versa is feasible provided that we restrict our attention to occurrence causal net.

**Proposition 14.** Let $U = \langle S, T, F, I, R, m, \ell \rangle$ be an occurrence causal net. Then $Q(U) = (T, \prec_U^+, \#_U)$ is a PES, and $\text{Conf}_{\text{cn}}(U) = \text{Conf}_{\text{PES}}(Q(U))$.

The following two theorems assure that the notion of (occurrence) causal net is adequate as the notion of occurrence net with respect to the classical notion of occurrence net in the relationship with prime event structure.

**Theorem 1.** Let $U = \langle S, T, F, I, R, m, \ell \rangle$ be an occurrence causal net such that $R = \emptyset$. Then $U = \mathcal{A}(Q(U))$.

**Theorem 2.** Let $\mathbf{P}$ be a PES. Then $\mathbf{P} = \mathcal{P}(\mathcal{A}(\mathbf{P}))$.

We end this section observing that if the causal net is injectively labeled, then the *event* labeling the transition happens just once.

# 5 Context-dependent event structures and causal nets

We are now ready to relate Context-dependent event structures and causal nets. We recall that in a Context-dependent event structure each event may happen in different context and thus each happening has a different operational meaning. Therefore we model each happening with a different transition and all the transitions representing the same happening bear the same label. Dependencies are inferred using inhibitor and read arcs, as it will be clear.

**Definition 18.** Let $\mathbf{E} = (\mathcal{E}, \#^*, \gg)$ be a simple CDES such that $\forall \mathbf{Z} \gg e$. $\text{CXT}(\mathbf{Z} \gg e)$ is finite. Define $\mathcal{B}(\mathbf{E})$ as the net $\langle S, T, F, I, R, m, \ell \rangle$ where

$$ - S = \{(*, e) \mid e \in \mathcal{E}\} \cup \{(e, *) \mid e \in \mathcal{E}\} \cup \{(\{e, e'\}, #) \mid e \neq e'\}, $$

$$ - T = \{(e, X, Y) \mid (X, Y) \in \mathbf{Z} \wedge \mathbf{Z} \gg e\}, $$

$$ - F = \{(s, (e, X, Y)) \mid s = (*, e) \lor (s = (W, #) \land e \in W)\} \cup \{((e, X, Y), s) \mid s = (e, *)\}, $$

$$ - I = \{(s, (e, X, Y)) \mid s = (e', *) \land e' \in \text{CXT}(\mathbf{Z} \gg e) \setminus (X \cup Y)\} \cup \{((s, (e, X, Y)) \mid s = (*, e') \land e' \in X\}, $$

$$ - R = \{(s, (e, X, Y)) \mid s = (e', *) \land e' \in Y\}, $$
$$- \mathbf{m} = \{(*, e) \mid e \in E\} \cup \{(\{e, e'\}, \#) \mid e \ \# \ e'\}, \text{ and}$$

$$- \ell : T \to E \text{ is defined as } \ell((e, X, Y)) = e.$$

We introduce a transition $(e, X, Y)$ for each pair $(X, Y)$ of the entry associated to the event $e$, and all these transitions are labeled with the same event $e$. All these transitions consume the token present in the place $(*, e)$ and put a token in the place $(e, *)$, thus just one transition labeled with $e$ can be fired in each execution of the net. Recall that the event $e$ is enabled at a configuration $C$ (here signaled by the places $(e', *)$ marked) if, for some $(X, Y) \in Z$, it holds that $\text{CXT}(Z \gg e) \cap C = X$ and $Y \subseteq C$. The inhibitor arcs assure that some of the events in $\text{CXT}(Z \gg e)$ have actually happened (namely the one in $X$) but the others (the ones in $\text{CXT}(Z \gg e) \setminus (X \cup Y)$) have not, and the $Y$ are other events that must have happened and this is signaled by read arcs. We cannot require $\text{CXT}(Z \gg e) \setminus X$ as some of the events there may be present in $Y$.

**Example 6.** Consider the cDES in Example 3, the corresponding causal net is the one depicted in Example 5. The event $c$ has two incarnations as the entry $\{(\emptyset, \{a\}), (\{b\}, \emptyset)\} \gg c$ has two elements: $(\emptyset, \{a\})$ and $(\{b\}, \emptyset)$.

**Example 7.** Consider the cDES of Example 4, the event $c$ has two incarnations as the entry $\{(\emptyset, \emptyset), (\{b\}, \{a\})\} \gg c$ has two elements, whereas $a$ and $b$ have one. The associated causal net is

<figure><img src="image_6.png" /></figure>

**Example 8.** Consider now the cDES in Example 2 (modeling the resolvable conflict of [27]).

<figure><img src="image_7.png" /></figure>
the actual implementation of this CDES into the causal net depicted before, where each event has three incarnations. The inhibitor and read arcs are colored depending on event they are related to.

The net obtained from a CDES using Definition 18 is indeed a causal net, and furthermore it is also conflict saturated.

**Proposition 15.** Let E be a CDES, and $\mathcal{B}(E)$ be the associated contextual Petri net. Then $\mathcal{B}(E)$ is a causal net and $\text{Conf}_{\text{CDES}}(E) = \text{Conf}_{\text{cn}}(\mathcal{B}(E))$.

**Proposition 16.** Let E be a CDES, and $\mathcal{B}(E)$ be the associated contextual Petri net. Then $\mathcal{B}(E)$ is conflict saturated.

For the vice versa we do need to make a further assumption on the causal net. The intuition is that equally labeled transitions are different incarnation of the same activity, happening in different contexts. Henceforth one has to make sure that the equally labeled transitions indeed represent the same *event* and each incarnation of an event should have the same *environment*, meaning with environment the events related to it (which in the CDES is calculated with CXT). Given a causal net $U = \langle S, T, F, I, R, \mathfrak{m}, \ell \rangle$ on a set of label $\mathcal{L}$ and a transition $t \in T$, with $\overrightarrow{\ell(t)}$ we denote the set of labels $\{a \in \mathcal{L} \mid s \in {}^{\circ}t \wedge \ell(s^\bullet) = a\}$, with $\overleftarrow{\ell(t)}$ the set of labels $\{a \in \mathcal{L} \mid s \in {}^{\circ}t \wedge \ell(\bullet s) = a\}$, and with $\tilde{\ell}(t)$ the set of labels $\{a \in \mathcal{L} \mid s \in \tilde{\ell}(t) \wedge \ell(\bullet s) = a\}$.

**Definition 19.** Let $U = (S, T, F, I, R, \mathfrak{m}, \ell)$ be a causal net labeled over $\mathcal{L}$, we say that $U$ is well behaved if

1. $\forall a \in \mathcal{L}. \forall t, t' \in \ell^{-1}(a) \text{ it holds that } \bullet t \cup \bullet t' = \{s\} \text{ and } t^\bullet \cup t'^\bullet = \{s'\}, \text{ and}$

2. $\forall a \in \mathcal{L}. \forall t, t' \in \ell^{-1}(a) \text{ it holds that } \overrightarrow{\ell(t)} \cup \overleftarrow{\ell(t')} = \{\tilde{\ell}\} \text{ and } \overrightarrow{\ell(t')} \cup \overleftarrow{\ell(t')} = \{\tilde{\ell}'\}$.

In a well behaved causal net all the transitions sharing equally labeled have a common input place and also a common output place (condition 1). The equally labeled transitions in the causal net are the various incarnation of the *event* they represent, thus they have the same context, though the various kind of involved arcs are different (condition 2).

*Example 9.* Consider the net below:

<figure><img src="image_8.png" /></figure>
The transitions labeled with c have the same environment, namely the set of labels {a, b}.

It is worth to observe that when associating a causal net to a CDES we obtain a
well behaved one.

**Proposition 17.** Let E be a CDES, and $\mathcal{B}(E)$ be the associated contextual Petri net. Then $\mathcal{B}(E)$ is a well behaved causal net.

To a causal net we can associate a triple where the relations will turn out to be, under some further requirements, those of a CDES. Here the events are the labels of the transitions, conflicts between events are inferred using the presets of the transitions and the entries are calculated using inhibitor and read arcs.

**Definition 20.** Let $U = (S, T, F, I, R, \mathfrak{m}, \ell)$ be a causal net labeled over $\mathcal{L} = E$. Define $\mathcal{R}(U) = (E, \gg, \#)$ as the triple where

$$- E = \ell(T),$$

$$- \forall e \in E. \mathcal{Z} \gg e \text{ where } \mathcal{Z} = \{(X, Y) \mid t \in T. \ell(t) = e \wedge X = \xrightarrow{\circ t} Y = \tilde{t}\}, \text{ and}$$

$$- \forall e, e' \in E. e \# e \text{ is there exists } t, t' \in T. \ell(t) \neq \ell(t') \text{ and } \bullet t \cap \bullet t' \neq \emptyset.$$

The construction above gives the proper CDES, provided that the cn is well behaved.

**Proposition 18.** Let $U = (S, T, F, I, R, \mathfrak{m}, \ell)$ be a well behaved causal net and $\mathcal{R}(U) = (E, \gg, \#)$ the associated triple, then $\mathcal{R}(U)$ is a CDES and $\text{Conf}_{\text{cn}}(U) = \text{Conf}_{\text{CDES}}(\mathcal{R}(U))$.

The following two theorems assure that the notion of (well behaved) causal net is adequate in the relationship with context-dependent event structure.

**Theorem 3.** Let $U = (S, T, F, I, R, \mathfrak{m}, \ell)$ be a well behaved causal net. Then $U = \mathcal{B}(\mathcal{R}(U))$.

**Theorem 4.** Let E be a CDES. Then E = $\mathcal{P}(\mathcal{B}(E))$.

# 6 Conclusions and future works

In this paper we have proposed the notion of causal net as the net counterpart of the context-dependent event structure, and shown that the notion is adequate. Like context-dependent event structure subsumes other kinds of event structures, also the new notion comprises other kinds of nets, and we have given a direct translation of occurrence nets into causal one, and also the usual constructions associating event structures to nets can be rewritten in this setting. Like context-dependent event structures, also causal nets have a similar drawback, namely the difficulty in understanding easily the dependencies among events, which in some of the event structures is much more immediate.
We have focussed on the objects and not on the relations among them, hence we have not investigated the categorical part of the new kind of net, which we intend to pursue in the future. Furthermore we have given a net counterpart without attempting to reduce its size, meaning that equivalent incarnations of an event are never identified, and finding appropriate equivalence to reduce the size would be quite useful.

Recently a notion of unfolding representing reversibility has been pointed out ([19]) and the issue of how find the appropriate notion of net relating *reversible* event structure has been tackled ([18]) and solved for a subclass of reversible event structure. The notion of causal net can be a basis for obtaining the more general result.

It should also be mentioned that *persistent* nets have been connected to event structures ([10] and [2]), and in these nets events may happen in different contexts, hence it would be interesting to compare these approaches to the one pursued here.

*Acknowledgements* The author wish to thank the anonymous reviewers for their useful suggestions and criticisms.

## References

1. Arbach, Y., Karcher, D.S., Peters, K., Nestmann, U.: Dynamic causality in event structures. Logical Methods in Computer Science 14(1) (2018), https://doi.org/10.23638/LMCS-14(1:17)2018

2. Baldan, P., Bruni, R., Corradini, A., Gadducci, F., Melgratti, H.C., Montanari, U. Event structures for petri nets with persistence. Logical Methods in Computer Science 14(3) (2018), https://doi.org/10.23638/LMCS-14(3:25)2018

3. Baldan, P., Busi, N., Corradini, A., Pinna, G.M.: Domain and event structure semantics for Petri nets with read and inhibitor arcs. Theoretical Computer Science 323(1-3), 129–189 (2004)

4. Baldan, P., Corradini, A., Montanari, U.: Contextual Petri nets, asymmetric event structures and processes. Information and Computation 171(1), 1–49 (2001)

5. Bartoletti, M., Cimoli, T., Pinna, G.M.: Lending Petri nets. Science of Computer Programming 112, 75–101 (2015), http://dx.doi.org/10.1016/j.scico.2015.05.006

6. Boudol, G.: Flow event structures and flow nets. In: Guessarian, I. (ed.) Semantics of Systems of Concurrent Processes. Lecture Notes in Computer Science, vol. 469, pp. 62–95. Springer (1990), https://doi.org/10.1007/3-540-53479-2_4

7. Casu, G., Pinna, G.M.: Flow unfolding of multi-clock nets. In: Ciardo, G., Kindler, E. (eds.) Petri Nets 2014. Lecture Notes in Computer Science, vol. 8489, pp. 170–189. Springer (2014), https://doi.org/10.1007/978-3-319-07734-5_10

8. Casu, G., Pinna, G.M.: Merging relations: A way to compact Petri nets' behaviors uniformly. In: Drewes, F., Martín-Vide, C., Truthe, B. (eds.) LATA 2017 Conference Proceedings. Lecture Notes in Computer Science, vol. 10168, pp. 325–337. Springer (2017), https://doi.org/10.1007/978-3-319-53733-7_24

9. Casu, G., Pinna, G.M.: Petri nets and dynamic causality for service-oriented computations. In: Seffah, A., Penzenstadler, B., Alves, C., Peng, X. (eds.) Proceedings of SAC 2017. pp. 1326–1333. ACM (2017), https://doi.org/10.1145/3019612.3019806
10. Crazzolara, F., Winskel, G.: Petri nets with persistence. Electronic Notes in Theoretical Computer Science 121, 143–155 (2005), https://doi.org/10.1016/j.entcs.2004.10.012

11. Fabre, E.: Trellis processes : A compact representation for runs of concurrent systems. Discrete Event Dynamic Systems 17(3), 267–306 (2007), https://doi.org/10.1007/s10626-006-0001-0

12. Fabre, E., Pinna, G.M.: Toward a uniform approach to the unfolding of nets. In: Bartoletti, M., Knight, S. (eds.) ICE 2018 Conference Proceedings. EPTCS, vol. 279, pp. 21–36 (2018), https://doi.org/10.4204/EPTCS.279.5

13. van Glabbeek, R.J., Plotkin, G.D.: Configuration structures, event structures and Petri nets. Theoretical Computer Science 410(41), 4111–4159 (2009), https://doi.org/10.1016/j.tcs.2009.06.014

14. Goltz, U., Reisig, W.: The non-sequential behavior of Petri nets. Information and Control 57(2/3), 125–147 (1983), https://doi.org/10.1016/S0019-9958(83)80040-0

15. Janicki, R., Koutny, M.: Semantics of inhibitor nets. Information and Computation 123, 1–16 (1995), https://doi.org/10.1006/inco.1995.1153

16. Khomenko, V., Kondratyev, A., Koutny, M., Vogler, W.: Merged Processes: a new condensed representation of Petri net behaviour. Acta Informatica 43(5), 307–330 (2006), https://doi.org/10.1007/s00236-006-0023-y

17. Langerak, R.: Bundle event structures: A non-interleaving semantics for lotos. In: Diaz, M., Groz, R. (eds.) FORTE '92 Conference Proceedings. IFIP Transactions, vol. C-10, pp. 331–346. North-Holland (1993)

18. Melgratti, H.C., Mezzina, C.A., Philipps, I., Pinna, G.M., Ulidowski, I.: Reversible occurrence nets and causal reversible prime event structures. In: Lanese, I., Rawski, M. (eds.) RC 2020 Conference Proceedings. Lecture Notes in Computer Science, vol. 11533, p. to appear. Springer (2020)

19. Melgratti, H.C., Mezzina, C.A., Ulidowski, I.: Reversing P/T nets. In: Nielson, H.R., Tuosto, E. (eds.) COORDINATION 2019. Lecture Notes in Computer Science, vol. 11533, pp. 19–36. Springer (2019), https://doi.org/10.1007/978-3-030-22397-7_2

20. Montanari, U., Rossi, F.: Contextual nets. Acta Informatica 32(6) (1995), https://doi.org/10.1007/BF01178907

21. Nielsen, M., Plotkin, G., Winskel, G.: Petri Nets, Event Structures and Domains, Part 1. Theoretical Computer Science 13, 85–108 (1981), https://doi.org/10.1016/0304-3975(81)90112-2

22. Pinna, G.M.: How much is worth to remember? a taxonomy based on Petri Nets Unfoldings. In: Kristensen, L.M., Petrucci, L. (eds.) PETRI NETS 2011. Lecture Notes in Computer Science, vol. 6709, pp. 109–128 (2011), https://doi.org/10.1007/978-3-642-21834-7_7

23. Pinna, G.M.: Representing dependencies in event structures. In: Nielson, H.R., Tuosto, E. (eds.) COORDINATION 2019 Conference Proceedings. Lecture Notes in Computer Science, vol. 11533, pp. 3–18. Springer (2019), https://doi.org/10.1007/978-3-030-22397-7

24. Pinna, G.M.: Representing dependencies in event structures. Logical Methods in Computer Science to appear (2020)

25. Pinna, G.M., Fabre, E.: Spreading nets: A uniform approach to unfoldings. Journal of Logical and Algebraic Methods in Programming 112, 100526 (2020), http://www.sciencedirect.com/science/article/pii/S2352220820300110

26. van Glabbeek, R.J., Plotkin, G.: Configuration structures. In: LICS '95. pp. 199–209. IEEE Computer Society Press (Jun 1995), https://doi.org/10.1109/LICS.1995.523257
27. van Glabbeek, R.J., Plotkin, G.D.: Event structures for resolvable conflict. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS’04 Conference Proceedings. Lecture Notes in Computer Science, vol. 3153, pp. 550–561. Springer (2004), https://doi.org/10.1007/978-3-540-28629-5_42

28. Winskel, G.: Event Structures. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) Petri Nets: Applications and Relationships to Other Models of Concurrency. Lecture Notes in Computer Science, vol. 255, pp. 325–392. Springer (1986), https://doi.org/10.1007/3-540-17906-2_31