Hernán Melgratti

Claudio Antares Mezzina

G Michele Pinna

A distributed operational view of Reversible Prime Event Structures

Reversible prime event structures extend the wellknown model of prime event structures to represent reversible computational processes. Essentially, they give abstract descriptions of processes capable of undoing computation steps. Since their introduction, event structures have played a pivotal role in connecting operational models (traditionally, Petri nets and process calculi) with denotational ones (algebraic domains). For this reason, there has been a lot of interest in linking different classes of operational models with different kinds of event structures. Hence, it is natural to ask which is the operational counterpart of reversible prime event structures. Such question has been previously addressed for a subclass of reversible prime event structures in which the interplay between causality and reversibility is restricted to the so-called causerespecting reversible structures. In this paper, we present an operational characterisation of the full-fledged model and show that reversible prime event structures correspond to a subclass of contextual Petri nets, called reversible causal nets. The distinctive feature of reversible causal nets is that causality is recovered from inhibitor arcs instead of the usual overlap between post and presets of transitions. In this way, we are able to operationally explain also out-of-causal order reversibility.

I. INTRODUCTION

Event structures are a well-established model of concurrency. They were originally proposed by Nielsen, Plotkin and Winskel [START_REF] Nielsen | Petri Nets, Event Structures and Domains, Part 1[END_REF] as an intermediate abstraction in between Scott domains (i.e., a denotational model) and Petri nets (i.e., an operational model). While Petri nets describe the behaviour of a system in terms of the consumption and production of data items (i.e., tokens) from repositories (i.e., places), an event structure consists of a set of event occurrences and constraints that regulate such occurrences (i.e., relations over events). Consider the Petri net N depicted in Figure 1a, which consists of five places s 1 , s 2 , s 3 , s 4 and s 5 , three transitions a, b and c and two tokens (depicted as bullets) respectively placed on s 1 and s 3 . The edges connecting places to transitions describe the consumption and production of tokens; e.g., the firing (i.e., execution) of b consumes a token from each s 2 and s 3 and produces a token in s 4 . The tokens available in N enable the firing of the transitions a and c but not that of b because there is no token in s 2 . That missing token is produced by the firing of a; hence, b can be fired only after a is so. For this reason, we Partially supported by the EU H2020 RISE programme under the Marie Skłodowska-Curie grant agreement 778233, by the French ANR project DCore ANR-18-CE25-0007 and by the Italian INdAM -GNCS 2020 project Sistemi Reversibili Concorrenti: dai Modelli ai Linguaggi, and by the UBA-CyT projects 20020170100544BA and 20020170100086BA. say that b causally depends on a. However, b can be fired only if c is not (and vice versa) because each transition requires a token from s 3 , which just contains one. In this case, we say that b and c are in conflict. An abstract description of the behaviour of N can be given in terms of an event structure, which consists of the definition of the causal dependencies and conflicts as binary relations over a set of events (each event represents a firing of a transition). A graphical representation is shown in Figure 1b, where causality (<) is drawn with straight lines (to be read from bottom to top) and binary conflicts (#) are represented by curly lines. In this case, b causally depends on a (i.e., a < b), while b and c are in conflict (i.e., b#c).

The behaviour associated with an event structure is understood in terms of a transition system defined over configurations (i.e., sets of events), as illustrated in Figure 1c. For instance, the transition ∅ → {a, c} indicates that the initial state ∅ (i.e., no event has been executed yet) may evolve to the state {a, c} by concurrently executing a and c. Note that neither {b} nor {a, b, c} are configurations because, on the one hand, b cannot occur without a and, on the other hand, b and c cannot occur in the same run of the system.

Since the seminal work by Winskel [27] that shows a tight connection (via a chain of correflections) between (the category of) safe nets and (prime) event structures, a lot of effort has been made to associate different guises of Petri nets with the corresponding class of event structures (e.g., [START_REF] Boudol | Flow Event Structures and Flow Nets[END_REF], [START_REF] Langerak | Bundle event structures: A non-interleaving semantics for lotos[END_REF], [START_REF] Casu | Flow unfolding of multi-clock nets[END_REF], [START_REF] Van Glabbeek | Configuration structures, event structures and Petri nets[END_REF] to name a few). Recently, event structures have been extended to account for reversible concurrent systems, namely a class of systems that have lately received lot of attention because of their applications in different fields [START_REF] Aman | Foundations of reversible computation[END_REF], [START_REF] Mezzina | Software and reversible systems: A survey of recent activities[END_REF], including programming abstractions for reliable systems [START_REF] Danos | Transactions in RCCS[END_REF], [START_REF] Medic | Towards a formal account for software transactional memory[END_REF], [START_REF] Lanese | Concurrent flexible reversibility[END_REF], program analysis and debugging [START_REF] Lanese | Causal-consistent replay debugging for message passing programs[END_REF], modelling bio-chemical simulations [START_REF] Kuhn | Reversibility in chemical reactions[END_REF] and quantum computing [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF].

The distinctive feature of a reversible system is that the execution of actions is liable to be undone. Reversible prime event structures (rPES) [START_REF] Phillips | Reversibility and asymmetric conflict in event structures[END_REF] accommodate the undoing of executed actions by allowing configurations to evolve by removing events. For instance, if c were an undoable event of the event structure P in Figure 1b, then the associated transition system would include the transition {a, c} → {a}. This is a disruptive feature in event structures since it breaks the underlying assumption by which configurations evolve by adding events. In fact, if X and Y are two configurations of an rPES then X → Y does not imply X ⊆ Y . As a consequence, the existing approaches to recover Petri nets out of event structures, even the most general ones [START_REF] Van Glabbeek | Event structures for resolvable conflict[END_REF], are not applicable. As a matter of fact, we still lack a procedure to associate a Petri net to a given rPES. Previous attempts [START_REF] Melgratti | Reversible occurrence nets and causal reversible prime event structures[END_REF] do this job just for the subclass of cause-respecting rPESes, i.e., rPESes that allow the reversing of an event once all events it caused have been reversed. For instance, the transition system associated with a cause-respecting reversible version of the event structure P in Figure 1b is depicted in Figure 2a. Note that each transition X → Y is paired with a reversing one Y → X; consequently, the configuration {a, b} can be reversed only by undoing first b and then a, i.e., {a, b} → {a} → ∅. Contrastingly, the transition {a, b} → {b} is not included because it accounts for the reversal of a before the reversal of the event b, which causally depends on a.

As shown in [START_REF] Melgratti | Reversible occurrence nets and causal reversible prime event structures[END_REF], the transition system of a causerespecting rPES can be implemented (concurrently / distributedly) as a Petri net where the undoing of events is achieved via reversing transitions, i.e., each transition t (corresponding to some event of the rPES) is accompanied by another transition t that undoes the effects of the firing of t, i.e., t (i) consumes the tokens produced by t; and (ii) produces the tokens consumed by t. The transition system in Figure 2a is implemented by the net N in Figure 2b, which is essentially the extension of N (Figure 1a) with the reversing transitions a, b and c.

This approach however falls short when addressing the full expressivity of rPESes, which accommodates different flavours of reversibility [START_REF] Aman | Foundations of reversible computation[END_REF], [START_REF] Mezzina | Software and reversible systems: A survey of recent activities[END_REF]. The reversing mechanism of an rPES is defined in terms of two relations (additional to the classical causality and conflicts): prevention and reverse causality. For instance, an rPES can stipulate that some event can be undone only when some other events have not occurred (prevention).

For instance, if we stipulate that c prevents the undoing of a (written c a), then {a, c} → {c} is banned from the transition system even though a is undoable and c does not causally depend on a. We can also specify that a particular event can be undone only when some other events have already occurred (reverse causality). For instance, if c is a reverse cause of a (written c ≺ a) then a cannot be reversed until c occurs, i.e., the transition {a} → ∅ is not admissible. We note that these constraints can be translated into Petri nets in the form of contextual arcs; in particular, inhibitor arcs [START_REF] Montanari | Contextual nets[END_REF], [START_REF] Baldan | Domain and event structure semantics for Petri nets with read and inhibitor arcs[END_REF] that prevent the firing of a transition if a token is present in some place of the net. For instance, the prevention c a can be represented in a Petri net with an inhibitor arc in a, as shown in Figure 3a; the added arc (depicted as ) forbids the firing of a when s 5 contains a token. Note that s 5 contains a token only when c has been fired, hence a cannot be fired if c has occurred. Along the same lines, the reverse causality c ≺ a can be represented as shown in Figure 3b: in this case, the inhibitor arc is connected to s 3 , which will contain a token if c has not been fired. Hence, a will be enabled only after c is fired.

Unfortunately, the previous observation is insufficient for capturing the full spectrum of rPESes due to the interplay among causality, prevention and reverse causality. This becomes clear when addressing rPESes enjoying out-of-causal order reversibility, which is typical in bio-chemical reactions [START_REF] Phillips | A reversible process calculus and the modelling of the ERK signalling pathway[END_REF]. Consider again the reversible system in Figure 1b. Assume now that a can be undone also in an out-of-causal order fashion, i.e., a can be reversed independently of the events that it may have caused (which in this case is b). Hence, the transition system would be extended to include the transition {a, b} → {b}, in which a is reversed even though b is not, and also {b} → {b, a}, in which the minimal event a is executed. When looking at the net N in Figure 2b, the transition {a, b} → {b} would require to be able to fire the reversing transition a also when the place s 2 does not contain any token (because the firing of b has consumed that token). Hence, a more involved definition of a would be needed for

s 1 s 2 s 3 s 4 s 5 s 6 a b c a < b b#c (a) N1 s 1 s 2 s 3 s 4 a b a b ≺ a (b) N2 s 1 s 2 s 3 s 4 a b a b a (c) N3
Fig. 4: Examples on how inhibitor acts ( arcs) can be used to model causality <, reverse causality ≺ and prevention relation among events handling the undoing of a. Moreover, after reversing a we should be able to fire a again, since the transition system associated to the rPES allows both {a} → ∅ → {a} and {a, b} → {b} → {a, b}. It should be noted that the execution of a has different effects in the two computations above: while the configuration {a} allows for the firing of b, the configuration {a, b} does not (because, b has been already fired). The way in which the causality relation between a and b is described in N (Figure 2b) would be insufficient to distinguish the cases above.

In this paper, we take a different approach by observing that inhibitor arcs can be used to model also causality. This simple idea is rendered by the net in Figure 4a, which is an operational counterpart of the event structure P in Figure 1b. The inhibitor arc in Figure 4a is used to model causality among the events a and b. Indeed, b can happen only after a has happened, hence a < b. As previously discussed, we represent prevention and reverse causality with inhibitor arcs, as illustrated in Figures 4b and4c. On the one hand, the inhibitor arc in Figure 4b models the reverse causality b ≺ a, i.e., a can be reversed only when b has been executed. On the other hand, the inhibitor arc in Figure 4c models prevention b a, i.e., the undoing of a cannot be executed if the event b has happened. A liberal usage of inhibitor arcs would not do the work. Therefore, we impose some (structural) constraints on nets to achieve our purpose, namely to identify a subclass of nets with inhibitor arcs that corresponds to reversible prime structures. The main contribution of our work is the definition of an operational interpretation of rPESes in terms of (a proper subclass of) Petri nets with inhibitor arcs, called reversible causal nets.

This paper is structured as follows: we start by recalling the basics of prime event structures and reversible prime event structures (Section II), and those of nets with inhibitor arcs (Section III). Then, we introduce causal nets, which are subclass of nets with inhibitor arcs, and show that they are a suitable counterpart of prime event structures (Section IV). In Section V, we introduce a reversible notion of causal nets and prove that they fully correspond to reversible prime event structures, thus giving a proper operational model of them. In Section VI we compare and discuss the relationship between a more classical operational model for prime event structures, namely occurrence nets, with our proposal, and illustrates the reasons that undermine the possibility of generalising occurrence nets to cope with richer models of reversibility as, e.g., out-of-causal order reversibility.

II. EVENT STRUCTURES

In this section we summarise the basics of prime event structures and reversible prime event structures by following the presentation in [START_REF] Phillips | Reversibility and asymmetric conflict in event structures[END_REF]. In what follows, we say that a binary relation < ⊆ A × A is an irreflexive partial order whenever it is irreflexive and transitive, and use ≤ to denote its reflexive closure. We write a < for the set {a ∈ A | a ≤ a} and shall omit the subscript < when it is clear from the context.

A. pre-PES and PES Pre-prime event structures are a relaxed form of prime event structures in which conflict heredity may not hold. They play a key role in the definition of reversible prime event structures.

Definition 1: A pre-prime event structure (pPES) is a triple P = (E, <, #), where

• E is a countable set of events;

• # ⊆ E × E is an irreflexive and symmetric relation, called the conflict relation; and • < ⊆ E × E is an irreflexive partial order, called the causality relation, defined such that ∀e ∈ E. e < is finite and ∀e , e ∈ e < . ¬(e # e ). We say a pPES P is a prime event structure (PES) when # is hereditary with respect to <, i.e., if e # e < e then e # e for all e, e , e ∈ E.

We write CF(X) when X ⊆ E is a conflict-free set of events, i.e., for all e, e ∈ X it holds that ¬(e # e ). Note that for all Y ⊆ X ⊆ E, CF(X) implies CF(Y ).

Example 1: Let P = (E, <, #) be defined such that

E = {a, b, c, d} # = {(a, b), (b, a)} < = {(b, c)}
It is immediate to check that # is irreflexive and symmetric, and < is an irreflexive partial order. Moreover, if e ∈ E and e = c then e = {e}, which is finite and conflict free. Additionally, c = {b, c}, which is also finite and conflict free. Hence, P is a pPES. However, P is not a PES because conflicts are not inherited along < because a#b < c but a#c does not hold. P would be a PES if # were defined as {(a, b), (b, a), (a, c), (c, a)}.

The following definition introduces the notion of (labelled) transitions between sets of events of a pPES.

Definition 2: Let P = (E, <, #) be a pPES and X ⊆ E a conflict-free set of events. We say

A ⊆ E is enabled at X if • A ∩ X = ∅ and CF(X ∪ A), and • ∀e ∈ A. if e < e then e ∈ X. If A is enabled at X, then X A -→ Y where Y = X ∪ A.
Example 2: Consider the pPES P in Example 1. The sets {a}, {b}, {d}, {a, d}, and {b, d} are all enabled at ∅ because they are all conflict free and they contain just minimal elements (according to <). Then, we can derive, e.g., the transitions ∅ {a} -→ {a} and ∅ {b,d} -→ {b, d}. On the contrary, neither {a, b} nor {c} are enabled at ∅. The former, because a and b are in conflict; the latter because ∅ does not contain b, which is a cause of c. Moreover, {c} is enabled at {b}, because the unique cause of c is b; consequently, {b} {c} -→ {b, c} holds. The notion of configurations of a pPES is formally defined below.

Definition 3: Let P = (E, <, #) be a pPES. A set of events X ⊆ E is a reachable configuration if it is conflict free, i.e., CF(X), and there exists a sequence A 1 , . . . , A n , such that X i Ai -→ X i+1 for all i, X 1 = ∅ and X n+1 = X. We write Conf pPES (P ) for the set of all reachable configurations of P .

We shall write Conf PES (P ) instead of Conf pPES (P ) when P is a PES.

Example 3: Consider again the pPES P in Example 1 and note that some conflict-free sets of events do not correspond to a state of the computation of P . For instance, the set {c, d}, which is conflict free, is not a configuration of P because it cannot be reached from the initial state ∅: c cannot be introduced to a configuration that does not contain b.

The following definition and result from [START_REF] Phillips | Reversibility and asymmetric conflict in event structures[END_REF] highlight that we can always recover a PES out of a pPES by making conflicts hereditary.

Definition 4: Let P = (E, <, #) be a pPES. Then hc(P ) = (E, <, ) is the hereditary closure of P , where is derived by using the following rules e # e e e e e e < e e e e e e e Proposition 1: Let P = (E, <, #) be a pPES, then

• hc(P ) = (E, ≤, ) is a PES, • if P is a PES, then hc(P ) = P , and • Conf pPES (P ) = Conf PES (hc(P )).

B. Reversible prime event structures

We now recall the notion of reversible prime event structure following the presentation in [START_REF] Phillips | Reversibility and asymmetric conflict in event structures[END_REF]. Reversible event structures extend PESes by allowing some of their events to be reversible or undoable. A reversible event u (implicitly) has an associated reversing event u capable of removing its effects, i.e., the execution of u followed by u cannot be observed. For this reason, the configurations of a reversible prime event structure may not evolve monotonically: reversible events can disappear to account for the fact that its reversing event has been executed. In order to account for different flavours of reversibility, a reversible prime event structure is equipped with two relations, dubbed prevention and reverse causality, dictating the way in which reversing events can be executed.

Definition 5: A reversible prime event structure (rPES) is a tuple P = (E, U, <, #, ≺, ) where (E, <, #) is a pPES, U ⊆ E are the reversible/undoable events (with reverse events being denoted by U = {u | u ∈ U } and disjoint from E, i.e., U ∩ E = ∅) and 1) ≺ ⊆ E × U is the reverse causality relation and it is such that u ≺ u for each u ∈ U and {e ∈ E | e ≺ u} is finite and conflict-free for every u ∈ U , 2)

⊆ E × U is the prevention relation defined such that ≺ ∩ = ∅, 3) the sustained causation is a transitive relation defined such that if e e then

• e < e ,

• if e ∈ U then e e, 4) # is hereditary with respect to : if e # e e , then e # e . The reverse causality relation prescribes the events that are required for the execution of each reversing event, i.e., e ≺ u says that u can be executed (or equivalently, u can be undone) only when e is present. Hence, the condition u ≺ u stands for the fact that an event u can be undone only when it is present in a configuration. The prevention relation models instead the cases in which an event can be reversed only if some other event is not in the configuration: e u means that u can be reversed only if e is not in the configuration.

Despite the underlying structure (E, <, #) is a pPES and, hence, conflicts may not be inherited through causality, the definition requires conflicts to be inherited through the new sustained causation relation , which is coarser that <, and accounts for the fact that the causes of some events may disappear from a configuration (see Example 8).

Example 4: Example 5: Let P 2 = (E, U, <, #, ≺, ) be a variant of P 1 above obtained by extending the definition of ≺ with the pair (d, c). In this case, the event c can be reversed only after d has been executed. This is an example of non-causal reversibility, in which concurrency interferes with reversibility: c can only be reversed if a concurrent (hence, unrelated) event is executed.

Let P 1 = (E, U, <, #, ≺, ) be an rPES defined such that E = {a, b, c, d} U = {b, c} < = {(b, c)} # = {(a, b), (b, a), (a, c), (c, a)} ≺ = {(b, b), (c, c))} = {(c
The following definition extends the notion of transitions between sets of events to account for reversing events.

Definition 6: Let P = (E, U, <, #, ≺, ) be an rPES and X ⊆ E be a set of events such that CF(X). For A ⊆ E and B ⊆ U , we say that A ∪ B is enabled at X if

• A ∩ X = ∅, B ⊆ X and CF(X ∪ A), • ∀e ∈ A, e ∈ E. if e < e then e ∈ X \ B, • ∀e ∈ B, e ∈ E. if e ≺ e then e ∈ X \ (B \ {e}), • ∀e ∈ B, e ∈ E. if e e then e ∈ X ∪ A. If A ∪ B is enabled at X then X A∪B -→ Y where Y = (X \ B) ∪ A.
Example 6: Consider the rPES P 1 introduced in Example 4.

We have, e.g., ∅ The reachable configurations of an rPES are the sets of events that can be reached from the empty set by performing events or undoing previously performed events, as stated below.

Definition 7: Let P = (E, U, <, #, ≺, ) be an rPES and X ⊆ E a conflict-free set of events, i.e., CF(X) holds. We say that X is a (reachable) configuration if there exist two sequences of sets A i and B i , for i = 1, . . . , n, such that

• A i ⊆ E and B i ⊆ U for all i, and • X i Ai∪Bi -→ X i+1 for all i with X 1 = ∅ and X n+1 = X.
The set of configurations of P is denoted by Conf rPES (P). We say that two rPESes P 1 and P 2 are equivalent, written A feature of rPESes that is challenging to accommodate in an operational model is the out-of-causal order reversibility, which is illustrated with the example below.

P 1 ≡ P 2 , if
Example 8: Consider P 3 = (E, U, <, #, ≺, ) as a variant of the rPES P 2 in Example 5 defined as follows

E = {a, b, c, d} U = {b, c} < = {(b, c)} # = {(a, b), (b, a)} ≺ = {(b, b), (c, c), (d, c)} = ∅
In this case, the induced sustained causation is empty, i.e., b c because b < c holds but c b does not. Since c b does not hold in P 3 , b can be reversed even when c, which causally depends on b, has been executed, e.g.,

∅ {b} -→ {b} {c} -→ {b, c} {b} -→ {c} {a} -→ {a, c}.
Note that the configuration {a, c} would be banned in standard PESes because a#b < c. However, it is allowed in rPESes because conflicts are not necessarily inherited through causality, which is essential to accommodate out-of-causal-order reversibility.

The previous examples highlight the main challenges to address when developing a net semantics for rPESes, which can be summarised as follows:

• configurations may drop events during computation, i.e., {b, c} {b} -→ {c} in P 3 ; • reachable configurations do not necessarily contain all the causes, e.g., the configuration {c} in P 3 does not contain b though b < c; • causes can be re-enabled, e.g., b is enabled at {c} in P 3 , however the re-execution of a disables b again, i.e., b is not enabled at {a, c}; • conflicts are not inherited through causality, as in P 3 ;

• reversibility induces dependencies on concurrent events, e.g., c in P 2 can be reversed only after the concurrent event d has been executed.

III. NETS

We start by recalling some notions that will be used throughout this paper. N denotes the set of natural numbers. A multiset over a set A is a function m : A → N. We assume multisets to be equipped with the usual operations of union In such cases, we write a ∈ m instead of m(a) = 0, and m ⊆ A if m(a) = 1 implies a ∈ A. Furthermore, we will use standard operations on sets, such as ∩, ∪ or \. The set of all multisets over A is denoted by µA. We write 0 for the unique multiset defined such that [[0]] = ∅.

A. Nets with inhibitor arcs

We summarise the basics of Petri net with inhibitor arcs along the lines of [START_REF] Montanari | Contextual nets[END_REF], [START_REF] Baldan | Domain and event structure semantics for Petri nets with read and inhibitor arcs[END_REF]. Given an IPT N = S, T, F, I, m and x ∈ S ∪ T , the preand postset of x are respectively defined as the (multi)sets

Definition 8: A Petri net is a 4-tuple N = S, T, F, m where S is a set of places, T is a set of transitions such that S ∩ T = ∅, F ⊆ (S × T ) ∪ (T × S)
• x = {y | (y, x) ∈ F } and x • = {y | (x, y) ∈ F }. If x ∈ S then • x ∈ µT and x • ∈ µT ; analogously, if x ∈ T then • x ∈ µS and x • ∈ µS. The inhibitor set of a transition t is the (multi)set • t = {s | (s, t) ∈ I}. The definition of • •, • • , • • generalise straightforwardly to multisets of transitions.
Example 9: Consider the simple IPT N 1 depicted in Figure 4a, which consists of six places depicted as circles and three transitions drawn as boxes. The flow relation is represented by black arrows while the inhibitor relation is shown by red lines ended with a small circle. The initial marking m = {s 1 , s 2 , s 3 } is represented by the bullets drawn within the corresponding places. Consider the transition b, which consumes tokens from s 2 and s 3 , produces a token in s 5 , and is inhibited by s 1 . Hence, its pre-, post-and inhibiting sets are respectively

• b = {s 2 , s 3 }, b • = {s 5 }, and • b = {s 1 }. A (multiset of) transition(s) A ∈ µT is enabled at a marking m ∈ µS, written m [A , whenever • A ⊆ m and ∀s ∈ [[ • A]]. m(s) = 0 ∧ A • (s) = 0.
The last condition requires the absence of tokens in all places connected via inhibitor arcs to the transitions in [[A]]. Observe that the multiset 0 is enabled at every marking. A (multiset of) transition(s) A enabled at a marking m can fire and its firing produces the marking m = m -• A + A • . The firing of A at a marking m is denoted by m [A m . We assume that each transition t of an IPT N is defined such that • t = ∅, i.e., it cannot fire spontaneously in an uncontrolled manner without consuming tokens.

Example 10: Consider the IPT introduced in Example 9 and note that both a and c are enabled at the initial marking m. On the contrary, b is not enabled because its inhibitor place s 1 contains a token. The firing of a produces the marking m = {s 2 , s 3 , s 4 }, i.e. m [a m , at which b becomes enabled because its preset s 2 and s 3 is marked while its inhibitor place

s 1 is not. A marking m is reachable in N if there exists a firing sequence σ = m [A 0 m 1 • • • m n [A n m
from the initial marking m to m. We write M N for the set of all reachable markings of N . A multiset of transitions X is a state of N if there exists a firing sequence Given a net N = S, T, F, m , we write < N for the transitive closure of F . We say N is acyclic if ≤ N is a partial order.

σ = m 0 [A 0 m 1 • • • m n-1 [A n m n such that X = 0≤i≤n A i .

IV. CAUSAL NETS

We now restrict our attention to the representation of causal dependencies through inhibitor arcs: we introduce a class of contextual Petri nets, dubbed causal nets, in which causality is recovered from the inhibiting relation instead of the usual flow relation. The main result in this section (Theorem 1) states that causal nets are an adequate operational counterpart of PESes. As a matter of fact, they are tightly connected with occurrence nets (as discussed in Section VI).

We define the relation between transitions t, t of an IPT by t t iff • t ∩ • t = ∅, i.e., the firing of t consumes (at least) one of the tokens that inhibit the firing of t . Similarly, we define by t t iff • t ∩ • t = ∅.

Definition 10: Let C = S, T, F, I, m be an IPT. C is a pre-causal net (pCN) if the following conditions are satisfied:

1)

< C ∩ (T × T ) = ∅; 2) [[T • ]] = T • ; 3) ∀t = t ∈ T. • t ∩ • t ∩ • T = ∅, 4) ∀t ∈ T . • t is finite; 5)
is an irreflexive partial order; 6) ∀t , t ∈ t . t t ⇒ t = t ; and 7) m = • T and • T ⊆ m. We say a pCN C is a causal net (CN) if it also satisfies the following condition

∀t, t , t ∈ T. t t ∧ t t ⇒ t t
The conditions imposed on CNs share motivations with those posed on occurrence nets, unravel nets [START_REF] Pinna | How much is worth to remember? a taxonomy based on Petri Nets Unfoldings[END_REF], [START_REF] Casu | Flow unfolding of multi-clock nets[END_REF], [START_REF] Casu | Petri nets and dynamic causality for serviceoriented computations[END_REF] and flow nets [START_REF] Boudol | Flow event structures and flow nets[END_REF], which are aimed at explaining computations without resorting to firing sequences. The first condition, which can be equivalently written as ∀t ∈ T. ∀s ∈ • t. • s = ∅, implies that causal dependencies in CNs do not arise because of the flow relation since t • ∩ • t = ∅ holds for all t, t ∈ T . The second condition ensures that there are no backward conflicts, i.e., a place belongs at most to the postset of one transition. The third one states that any place appearing in the preset of at least two transitions cannot be connected via inhibitor arcs to other places of the net. In this way, we ban or-causality, i.e., situations in which the firing of a transition may have different causes. In combination with the fourth requirement, they ensure that each transition has a finite set of causes, i.e., the set {t ∈ T | t t} is finite. The fifth condition avoids cycles in the dependencies arising from inhibitor arcs. Since is irreflexive, none of the transitions is blocked (i.e.,

• t∩ • t = ∅ for all t). The sixth condition is reminiscent of the requirement of pPES by which inheritance of conflicts holds locally, i.e., any pair of different transitions t , t in t are not in conflict. The last requirement states that the preset of all transitions are initially marked (i.e., m = • T ). Moreover,

• T ⊆ m together with the first requirement imply that inhibitor places cannot appear in the postset of any transition.

The additional condition for CNs imposes conflict inheritance along the relation (recall that conflicts are modelled through shared input places).

Example 12: The IPT C 1 depicted in Figure 5a is a pCN, as discussed below. Conditions 1 and 2 of Definition 10 hold because every place appearing in the postset of some transition has exactly one incoming and none outgoing arc. The only place that belongs to the preset of at least two transitions is s 2 . However, there is no inhibitor arc connected to s 2 . Hence, Condition 3 also holds. Condition 4 follows immediately because there is just one inhibitor arc. The induced causality relation is the irreflexive partial order = {(b, c)}, which satisfies Condition 5. If t ∈ T and t = c then t = {t}. We remark that C 1 is not a CN because conflicts are not inherited along . In fact, a b and b c but a c. The IPT C 2 in Figure 5b, which makes explicit the conflict between a and c, is a CN.

Definition 11: Let C = S, T, F, I, m be a pCN. A set of transitions X ⊆ T is a configuration of C if:

• ∀t, t ∈ X.t t ⇒ t = t (conflict freeness), and • ∀t ∈ X. t ⊆ X (left closedness with respect to ). The set of configurations of a pCN C is denoted by Conf pCN (C).

Should C be a CN, we write Conf CN (C) in lieu of Conf pCN (C).

Example 13: Consider the pCN C 1 and the CN C 2 in Figure 5. Their sets of configurations coincide and are shown below

Conf pCN (C 1 ) = Conf CN (C 2 ) = {{a}, {b}, {d}, {a, d}, {b, c}, {b, d}, {b, c, d}}
There is a close correspondence between the configurations of a pCN and its reachable markings: any reachable marking determines a configuration of the net and vice versa. This is formally stated by the proposition below.

Proposition 2: Let C = S, T, F, I, m be a pCN. Then, Fig. 6:

1) if m ∈ M C then • m ∈ Conf pCN (C); and 2) if X ∈ Conf pCN (C) then m -• X + X • ∈ M C .
A(P) m -• X + X • = {s 1 , s 4 , s 7 , s 9 } = m is a reachable marking of C 2 .
The notion of equivalence for causal nets specialises to configurations, i.e.,

C 1 ≡ C 2 iff Conf pCN (C 1 ) = Conf pCN (C 2 ).

A. From pPESes to pCNs

We now show that every pPES can be associated with a pCN that has the same configurations. We start by introducing the mapping A from pPESes to pCN.

Definition 12: Let P = (E, <, #) be a pPES. The associated pCN is A(P) = S, E, F, I, m where The construction associates the pPES P with a pCN that has as many transitions as events are in P. Places are identified with pairs, which may have one of the following forms: (i) ( * , e) for the precondition of e, (e, * ) for the postcondition of e, and ({e, e }, #) for the conflict e # e . The flow relation is defined so that each transition e consumes tokens from ( * , e) and every (W, #) where e ∈ W ; and only produces a token in (e, * ). Different from the classical construction of occurrence nets out of PESes [START_REF] Winskel | Event Structures[END_REF], places do not convey causal dependencies, which are modelled here via inhibitor arcs: if e causally depends on e (i.e., e < e), then there is an inhibitor arc between the transition e and the place ( * , e ), i.e., a place of the preset of e . The initial marking m assigns a token to any place appearing in the preset of a transition.

Example 15: Let P = (E, <, #) be a pPES where

E = {a, b, c, d} < = {(b, c)} # = {(a, b), (b, a), (a, c), (c, a)}
The associated pCN is shown in Figure 6. Note that the transition c is not enabled because of the inhibitor arc from ( * , b); all remaining transitions are enabled; also a and b are in conflict because they both consume from ({a, b}, #).

The adequacy of A is formally stated by showing the equivalence of the respective sets of configurations.

Proposition 3: Let P is a pPES. Then, A(P) is a pCN and Conf pPES (P) = Conf pCN (A(P)).

Corollary 1: Let P be a PES. Then A(P) is a CN and Conf PES (P) = Conf CN (A(P)).

B. From pCNs to pPESes

The definition of the mapping Q from pCNs to pPESes relies on the facts that is an irreflexive partial order, and conflicts are locally preserved in a pCN.

Definition 13: Let C = S, T, F, I, m be a pCN. The associated pPES is Q(C) = (T, , #) where Corollary 2:

# = {(t, t ) | t = t ∈ T ∧ t t }.
Let C be a CN. Then Q(C) is a PES and Conf PES (Q(C)) = Conf CN (C).
The following result ensures that the notion of causal nets is adequate for PESes. It is obtained by combining Proposition 3 and Corollary 1 (in Section IV-A) with Proposition 4 and Corollary 2 above.

Theorem 1: Let C be a causal net. Then C ≡ A(Q(C)). Let P be a PES. Then P ≡ Q(A(P)).

V. REVERSIBLE CNS AND REVERSIBLE PESES

In this section we introduce a reversible version of pCNs and show that they are an operational counterpart for rPESes.

A. Reversible causal nets

The intuition behind the definition of a reversible causal net is that of extending a (pre) causal net with transitions, dubbed backward, that reverse / undo the effects of previously fired ordinary transitions, which we call forward. Given an IPT N = S, T, F, I, m and a transition t ∈ T , we write S t for the set of places {s ∈ S | s ∈ • t ∧ s • = {t}}, i.e., the places in the preset of t that do not appear in the preset of other transitions.

Definition 14: An IPT V = S, T, F, I, m is a reversible causal net (rCN) if there exists a partition {T , T } of T , with T the forward transitions and T the backward ones, such that:

1) S, T , F |T ×T , I |T ×T , m is a pCN net; 2) [[ • T ]] = • T and ∀t ∈ T . ∃! t ∈ T such that t • = • t, • t = t • , and S t ∩ • t = ∅; 3) ∀t ∈ T . K = {t | t ∈ T ∧ • t ∩ • T = ∅} is finite and [[ • K]] = • K; 4) ∀t ∈ T .∀t ∈ T . if • t ∩ • t = ∅ then t • ∩ • t = ∅; 5) ≪ ⊆ T × T is a transitive relation defined such that t ≪ t if t t and if there exists t ∈ T such that • t = t • then • t ∩ t • = ∅; and 6) ∀t, t , t ∈ T . • t∩ • t = ∅ ∧ t ≪ t ⇒ • t∩ • t = ∅.
We write V T for an rCN V with backward transitions T . The first condition states that the subnet consisting of just forward transitions is a pre causal net. The second one establishes that each backward transition t reverses exactly one forward transition t; consequently, t consumes the tokens produced by t (i.e., t • = • t) and produces the tokens consumed by t (i.e., t • = • t); the condition S t ∩ • t = ∅ ensures that t causally depends on t. By requiring [[ • T ]] = • T , we ensure that a forward transition has at most one reversing transition. The remaining conditions recast the ones imposed on rPES, where inhibitor arcs are used to model the reverse causality relation (≺) and the prevention relation ( ): when an inhibitor arc connects a backward transition with a place in the preset of some forward transition, then the modelled relation is the reverse causality; on the contrary, prevention is represented by linking a backward transition to a place in the the postset of a forward transition. Consequently, the third condition can be read just as requiring each backward transition to causally depend on a finite number of forward transitions (i.e., the ones in K); which moreover should be conflict free (i.e., they do not share places in their preset). By the fourth condition, a backward transition t causally dependant on a forward transition t (i.e., • t ∩ • t = ∅) cannot be prevented by the same transition (i.e., t • ∩ • t = ∅). The relation ≪ defined by the fifth condition is analogous to the sustained causation, i.e., it coincides with causality only when prevention enforces causal reversibility. The last condition states that conflicts are inherited along ≪.

Example 17: Consider the IPT V in Figure 7, which is an rCN with reversing transitions T = {b, c}. First note that S, T , F |T ×T , I |T ×T , m is the CN C 2 shown in Figure 5b. There are two backward transitions: b, for reversing b, and c for reversing c. Each of them reverses the markings of its associated forward transition, e.g., b consumes from s 7 and produces on s 2 and s 3 . The inhibitor arcs connecting s 3 to b and s 4 to c reflect causality, e.g., b causally depends on b. In this case the behaviour of the net would remain unaltered if such inhibitor arcs were omitted. However, we require them in order to uniformly capture causality in terms of instead of resorting to the flow relation. The inhibitor arc connecting s 5 to c also accounts for causality: c cannot be fired until d is fired and the token in s 5 is consumed. The inhibitor arc connecting s 8 to b models prevention since b is not enabled if s 8 is marked (i.e., if c has been fired).

B. From rPESes to rCNes

This section introduces a mapping from rPESes to rCNes. (We prove the adequacy of its definition in Section V-D.)

Definition 15: Let P = (E, U, <, #, ≺, ) be an rPES. Then, A r (P) = S, T, F, I, m where A(E, <, #) = S, T , F , I , m and 1) The construction uses the mapping A( ) for obtaining a pCN out of the underlying pPES consisting of just forward events, which is then extended with as many backward transitions as reversible events in P. A backward transition (u, r), which reverses u, is defined such that its preset is the postset of u, and its poset is the preset of u. Inhibitors arcs are as expected: the reverse causality e ≺ u translates into an arc connecting the backward transition (u, r) to the enabling condition of e, i.e., ( * , e); the prevention e u is mapped to an arc connecting (u, r) to the post condition of e, i.e., (e, * ).

T = T ∪ {(u, r) | u ∈ U }; 2) F = F ∪ {(s, (u, r)) | s ∈ u • } ∪ {((u, r), s) | s ∈ • u}; 3
Example 18: Consider the rPES P 1 = (E, U, <, #, ≺, ) in Example 4. Note that (E, <, #) and its associated CN are the ones discussed in Example 15. Then, A r (P 1 ), which is shown in Figure 7, is obtained by extending the CN in Figure 6 with the transitions (b, r) and (c, r) corresponding to the reversing events b and c. The inhibitor arcs from (b, * ) to (b, r) and (c, * ) to (c, r) indicate that the backward transitions are enabled only after the corresponding forward transitions are fired. The inhibitor arc from ( * , c) to (b, r) indicates that b cannot be fired if c has been executed.

The rCN A(P 3 ) associated with the rPES P 3 in Example 8 is depicted in Figure 9. Note the absence of the place ({a, c}, #) (because a and c are not in conflict in P 3 ) and the inhibitor arc from ( * , c) to (b, r) (since b can be reversed even when ( * , c) is marked). Moreover, the inhibitor arc from (d, * ) to (c, r) prevents c to be reversed until d is fired.

The encoding of the rPES P 2 in Example 5 produces a net isomorphic to the one shown in Figure 7 (just places and transitions are named differently).

Proposition 5: If P is an rPES then A r (P) is an rCN.

C. From rCNes to rPESes

The encoding of rCNs into rPESes is given below. Definition 16: Let V T = S, T, F, I, m be an rCN with backward transitions T . Then, Q r (V T ) = (E, U, <, #, ≺, ) where:

1

) E = T \ T ; 2) U = {t | t ∈ T ∧ t ∈ T ∧ • t = t • }; 3) < = |E×E ; 4) # = {(e, e ) | e = e ∈ E ∧ e e }; 5) ≺= {(t, t ) | t ∈ E ∧ t ∈ T ∧ • t ∩ • t = ∅}; 6) = {(t, t ) | t ∈ E ∧ t ∈ T ∧ t • ∩ • t = ∅}.
The construction maps an rCN V T to an rPES whose events are the forward transitions T \ T of V T . Only the forward transitions that have a reversing transition in T are undoable events (i.e, they belong to U ). The causality < and conflict # relations are obtained as the proper restrictions of those defined on V T . Finally, the reverse causation ≺ and the prevention are recovered from inhibitor arcs.

Example 19: Consider the rCN in Figure 7. The events of the associated rPES are {a, b, c, d}, from which {b, c} are reversible. The only causal dependency is b c. Conflicts are induced from shared places in the presets of transitions, which in this case are s 0 and s 2 . Hence, a#c and b#d. The inhibitor arc connecting s 3 to b is mapped to the reverse causality b ≺ b because s 3 belongs to the preset of b. Analogously, the arc from s 4 to c (resp., from s 5 to c) is mapped to c ≺ c (resp., d ≺ c). On the contrary, the arc from s 8 to b gives c b because s 8 belongs to the postset of c. Hence, the obtained rPES is the one defined in Example 5.

Proposition 6:

If V T is an rCN then Q r (V T
) is an rPES.

D. rCNes and rPESes correspondence

We show that the mappings introduced in the previous sections establish a tight correspondence between rPESes and rCNs in terms of configurations.

Definition 17: Let V T = S, T, F, I, m be an rCN. A pre-configuration X of V T is a conflict-free set of forward transitions, i.e., X ⊆ T \ T and ∀t, t ∈ X.

• t ∩ • t = ∅ ⇒ t = t . Its associated marking is m X = m -• X + X • .
If X is pre-configuration of V T , observe that m X may not be a reachable marking. For instance, the pre-configuration {c, d} of the rCN in Figure 7 has the associated reachable marking m X = {s 1 , s 2 , s 3 , s 8 , s 9 } which is not reachable because c cannot be fired if s 3 is marked.

Definition 18: A pre-configuration X of an rCN V T is a configuration if m X is a reachable marking of V T . We write Conf rCN (V T ) for the set of all configurations of V T .

The remaining results in this section establish the operational correspondence between rPESes (resp., rCNs) and their associated rCNs (resp., rPESes). We start by showing that a set of events is enabled at a configuration X of P if and only if the corresponding set of transitions is enabled at the marking m X of A r (P).

Lemma 1: Let P = (E, U, <, #, ≺, ) be an rPES and X ⊆ E a conflict-free set of events.

• If A∪B is enabled at X then m X [A ∪ {(u, r) | u ∈ B} holds in A r (P). • If Y ⊆ E ∪ (U × {r}) is a set of transitions of A r (P) such that m X [Y then (Y ∩ E) ∪ {u | (u, r) ∈ Y } is enabled at X.
As a consequence of the above result, we have the operational correspondence for A r ( ) as stated below.

Theorem 2: Let P be an rPES. Then, X ∈ Conf rPES (P) iff X ∈ Conf rCN (A r (P)).

We proceed analogously for Q r ( ) to show that the encoding preserves both enabling and configurations.

Lemma 2: Let V T = S, T, F, I, m be an rCN, X ⊆ T \ T a pre-configuration of V T , A ⊆ T \ T a set of events, B = {t | t ∈ B} a set of reversing events, with B ⊆ T \ T .

• If m X [A ∪ B then A ∪ B is enabled at X in Q r (V T ). • If A ∪ B is enabled at X in Q r (V T ) then m X [A ∪ B . Theorem 3: Let V T be an rCN. X ∈ Conf rCN (V T ) iff X ∈ Conf rPES (Q r (V T )).
From the previous results, we conclude that rCNs are a proper counterpart of rPESes.

Theorem 4: If V T is an rCN then V T ≡ A r (Q r (V T )). If P is an rPES then P ≡ Q r (A r (P)).

VI. CAUSAL NETS AND OCCURRENCE NETS

The developments in Sections IV-A and IV-B have shown that CNs are an adequate counterpart for prime event structures (Theorem 1). We now study the connections between CNs and occurrence nets, which are standardly associated with PESes. Finally, we provide further evidence suggesting that occurrence nets cannot be easily adapted to model out-ofcausal order reversibility.

We start by introducing some notions about nets that will be used throughout this section. An IPT N is single execution if its states are sets, i.e., ∀X ∈ St(N ).X = [[X]]. Intuitively, each transition of a single execution net can be fired at most once in a firing sequence. Single execution nets (albeit without inhibitor arcs) are also known as 1-occurrence nets [START_REF] Van Glabbeek | Configuration structures[END_REF], [START_REF] Van Glabbeek | Configuration structures, event structures and Petri nets[END_REF]. The net N 1 in Figure 4a is single execution.

An IPT is said conflict-saturated whenever any pair of transitions that do not appear in any firing sequence of the net have a common place in their presets.

Definition 19: Let N = S, T, F, I, m be an IPT. Two transitions t, t ∈ T are in conflict if they do not simultaneously appear in any state of N , i.e., {t, t } ⊆ [[X]] for all X ∈ St(N ).

N is conflict-saturated whenever for all t, t ∈ T , if t and t are in conflict then • t ∩ • t = ∅.

A conflict-saturated net is one in which conflicts are characterised structurally.

Example 20: The net in Figure 10 is conflict-saturated because the pairs a and c, as well as b and c, do no appear in any configuration of the net but each pair of transitions shares a place in their preset (s 7 for a and c, and s 3 for b and c). Then, the conflict-saturated version of N is given by N confl(N ) = S , T, F , I, m where

• S = S ∪ {s T | T ∈ confl(N )}, • F = F ∪ {(s T , t) | t ∈ T }; • m = m ∪ {s T | T ∈ confl(N )}.
It should be noted that for each transition t ∈ T and each reachable marking m ∈ M N such that m [t , there exists a reachable marking m ∈ M N confl(N ) such that m [t and ∀s ∈ S. m (s) = m(s), i.e., the transformation preserves the behaviour despite m and m may differ in the added places. The correspondence holds also in the opposite direction: for each transition t ∈ T and each reachable marking m ∈ M N confl(N ) such that m [t , there exists a reachable marking m ∈ M N such that m [t and ∀s ∈ S. m (s) = m(s).

The construction above gives a procedure for obtaining an equivalent, conflict-saturated version of an IPT.

Proposition 7: Let N be a single execution IPT, then there exists a conflict-saturated IPT N confl(N ) such that N confl(N ) ≡ N .

Remark 1: It is worth stressing that pCNs and CNs are single execution nets; moreover, CNs are also conflict-saturated.

A. Occurrence nets

We recall the notion of occurrence nets 1 . We adopt the usual convention by which places and transitions are called conditions and events; and write B and E for their respective sets (instead of S and T ) and c for the initial marking. We may confuse conditions with places and events with transitions. Moreover, we will omit the inhibiting relation I since occurrence nets do not have inhibitor arcs (i.e., I = ∅). As for Proposition 7, every single execution IPT can be converted into an equivalent conflict-saturated net. Since the construction does not modify the inhibitor relation, the same holds for occurrence nets.

Definition 21: Let O = B, E, F, c be an ON. A set of events X ⊆ E is a configuration of O if:

• ∀e, e ∈ X.e = e ⇒ ¬(e # e ), i.e., it is conflict-free; and • ∀e ∈ X. e ⊆ X, i.e., it is left-closed. The set of configurations of O is denoted by Conf ON (O). If a ON is conflict-saturated then the first condition can be rewritten as ∀e, e ∈ X. • e ∩ • e = ∅ ⇒ e = e . Moreover, observe that each configuration of an ON is also a state.

B. From ON to CN

We show that every occurrence net can be turned into a causal one, and hence that the latter notion is a conservative extension of the former one.

Definition 22: Given an occurrence net O = B, E, F, c we can associate to it a net O(O) defined as S, E, F , I, m where 1 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 nonsequential semantics of a net, and each reachable marking of the occurrence net corresponds to a reachable marking of the unfolded net. Here we focus purely on occurrence nets and not on the nets they are the unfoldings of, nor on the relation between the net and its unfolding. each event e of an occurrence net is associated with an homonymous transition and two places ( * , e) and (e, * ) in the corresponding causal net. When marked, ( * , e) represents the fact that e has not been fired yet, while (e, * ) describes the fact that e has been executed. Moreover, there is one additional place ({e, e }, #) for any pair of conflicting events e#e in O. As expected, the preset of an event e consists of the place ( * , e) and all the places of the form ({e, e }, #), which represent the conflicts of e with some other event e . Causal dependencies are mapped into inhibitor arcs so that (e , * ) belongs to the inhibitor set of e only if e causally depends on e in O. The initial marking assigns a token to every place belonging to the the preset of some transition.

Example 21: Figure 11 shows the encoding of the ON O in Figure 11a as the CN O(O) in Figure 11b. We stress that O(O) is conflict-saturated for any ON O.

C. From pCN to ON

The encoding from pCNs to ONs basically requires to embed causal dependencies expressed in terms of inhibitor arcs into the the flow relation. For this reason, the encoding incorporates new places of the form (t, t ) as a way for representing the dependency t t .

Definition 23: Let C = S, T, F, I, m be a pCN. The associated ON is a net Z(C) = B, T, F , c where

• B = S ∪ {(t, t ) | t t }; • F = F ∪ {(s, t) | s = (t , t)} ∪ {(t, s) | s = (t, t )}; and • c : B → N is such that c(b) = m(b) if b ∈ S and c(b) = 0 if b ∈ S.
Note that the flow relation is extended to account for causal dependencies: each transition t produces tokens in the places (t, t ) (i.e., (t, (t, t )) ∈ F ) and consumes tokens from (t , t) (i.e., (t, (t , t))). In this way, a transition t is enabled when all its causes have been already fired (i.e., the places (t , t) are marked).

The following results highlights that the transformation preserves the behaviour of the net.

Proposition 10: Let C be a pCN, then Z(C) is an ON and C ≡ Z(C). The net Z(C) in not necessarily conflict-saturated, as C could be not conflict-saturated.

Example 22: In Figure 12 we depict a pCN C (on the left) and the associated ON (on the right). Despite we can directly obtain a PES from an ON (and vice versa) [START_REF] Winskel | Event Structures[END_REF], the mappings introduced in Sections IV-A and IV-B give us an alternative procedure that relies on the intermediate representation of PESes in terms of CNs, as stated below.

D. Reversible occurrence net

A causal-consistent reversible version of ONs has be proposed in [START_REF] Melgratti | Reversing Place Transition Nets[END_REF], [START_REF] Melgratti | Reversible occurrence nets and causal reversible prime event structures[END_REF]. The model associates each reversible event of an occurrence net with a reversing transition, analogously to our rCNs. As already noticed in [START_REF] Melgratti | Reversible occurrence nets and causal reversible prime event structures[END_REF], this approach fails when considering the full generality of rPES due to the tight correspondence between the configurations of an occurrence net and their associated reachable markings: given an ON O = B, E, F, c and a configuration X, its associated reachable marking m X can be computed as

(c ∪ [[X • ]]) \ [[ • X]]
This equation makes clear that some effects (i.e., the produced tokens) of the executed events may not be observable on the reachable marking, i.e., if e ∈ X and e • ∩ • X = ∅, then e • ⊆ m X . This is the case for the configuration {b, c} of the ON depicted in Figure 12b, where the condition (b, c) is used by the firing of c, and does not hold after c is executed. Assume that we expect b to be an out-of-causal-order reversible event and add the reversing transition b that consumes from s 4 and (b, c). Then it is clear that b is not enabled at m X ; hence, the undoing of b would require the undoing of c, which imposes a causally-order reversibility model.

VII. CONCLUSIONS

The main contribution of this paper is the characterisation of a class of Petri nets with inhibitor arcs, dubbed reversible causal nets (rCN), which provides an operationally counterpart for the reversibility model behind reversible prime event structures (rPES) [START_REF] Phillips | Reversibility and asymmetric conflict in event structures[END_REF]. The key observation is that three out of the four (primitive) relations that rPESes define over events can be captured by inhibitor arcs: both forward and reverse causality can be modelled as inhibitor arcs that connect an event (either forward or reversing) to (some of the conditions in) the presets of its immediate causes, while prevention is translated to arcs that connect an event to (some of the conditions in) the postsets of the preventing events. The remaining conflict relation corresponds, as usual, to overlapped presets.

Figure 13 briefly recaps our results with respect to the state of the art. The correspondence between occurrence nets and prime event structures is due to Winskel's seminal work [START_REF] Winskel | Event Structures[END_REF]. We have introduced a new class of Petri nets, called causal nets, and showed their correspondence with prime event structures (Theorem 1). We have then presented the reversible variant of causal nets (rCNs), and showed that they are an operational counterpart of the reversible prime event structures of [START_REF] Phillips | Reversibility and asymmetric conflict in event structures[END_REF] (Theorem 4). Finally, we showed that causal nets are tightly connected to occurrence nets (Theorem 5), and give a revisitation of Winskel's correspondence via Theorem 6. To give a complete picture of known results, we depict the extension of occurrence nets into reversible occurrence nets proposed in [START_REF] Melgratti | Reversible occurrence nets and causal reversible prime event structures[END_REF]; where the latter ones correspond to a proper subclass of rPES that just accounts for causally-consistent reversibility (crPES).

Besides contributing to the well-established line of work initiated in [START_REF] Nielsen | Petri Nets, Event Structures and Domains, Part 1[END_REF], [START_REF] Winskel | Event Structures[END_REF] that links classes of nets with classes of event structures, our work explains the reversing mechanisms of rPESes by relying on a well-studied concurrent model. In this respect, our contribution constitutes a step forward with respect to [START_REF] Melgratti | Reversible occurrence nets and causal reversible prime event structures[END_REF], which just deals with the subclass of causalreversible rPESes which, e.g., do not provide out-of-causalorder reversibility. Remarkably, our reversible causal nets do not appeal to original elements to achieve reversibility as, e.g., the bonds of [START_REF] Philippou | Reversible computation in petri nets[END_REF]. As a matter of fact, causal nets do not rely either on the information (i.e., colours) carried on by tokens (as done in [START_REF] Barylska | Reversing computations modelled by coloured petri nets[END_REF], [START_REF] Melgratti | Reversing Place Transition Nets[END_REF]).

The characterisation of rPESes as restrictions over the structure of the nets enables the study of less constrained models. For instance, an undoable event in an rPES can be undone just by performing one reversing event. This excludes the possibility of defining alternative conditions for reversing an event. We can overcome this limitation in the operational model just by dropping the requirement of non-overlapping backward transitions (i.e., [[ • T ]] = • T ). This kind of analysis seems an interesting line to explore in future work.

Causal nets and their reversible versions play a role analogous to occurrence nets (in their connection with PESes). Consequently, we may ask ourselves about the class of (reversible) nets whose unfoldings are (reversible) causal nets, or, alternatively, which are the suitable categories that would allow us, if possible, to extend Winskel's chain of coreflection to reversible event structures.

Fig. 1 :

 1 Fig. 1: A simple Petri net and its associated Event Structure

Fig. 2 :

 2 Fig. 2: Causal-consistent reversible version of N

Fig. 3 :

 3 Fig. 3: Prevention and reverse causality operationally

  , b)} While b and c are reversible in P 1 , a and d are not because a, d ∈ U . Moreover, c causally depends on b because b < c; and a is in conflict with both b and c because of the definition of #. Consequently, d is concurrent w.r.t. a, b and c. The definition of the reverse causality contains the expected pairs stating that each reversible event can be undone only if it has been executed (i.e., b ≺ b and c ≺ c). The definition of the prevention relation states that b cannot be reversed if c has been executed, i.e., c b, which is typical of causal reversible models. In this example, sustained causation coincides with causality, i.e., = <, since b c holds because b < c and c b do so. Note that conflicts are inherited along the sustained causation (and also causality), i.e., a#b < c and a#c.

  , c, d}. Consider now the rPES P 2 in Example 5, and note that the set {d, c} is not enabled at {b, c}: despite c is present, the reverse causality d ≺ c states that d is also required for the reversing of c.

  (+) and difference (-), and write m ⊆ m if m(a) ≤ m (a) for all a ∈ A. We shall write [[m]] for the underlying set of a multiset m, i.e., the multiset defined such that [[m]](a) = 1 if m(a) > 0 and [[m]](a) = 0 otherwise. We often confuse a multiset m with the set {a ∈ A | m(a) = 0} when m = [[m]].

  is the flow relation, and m ∈ µS is the initial marking. Definition 9: A Petri net with inhibitor arcs (IPT for short) is a tuple N = S, T, F, I, m , where S, T, F, m is a Petri net, and I ⊆ S × T is the inhibiting relation.

Fig. 5 :

 5 Fig. 5: Two pre-causal nets

Example 14 :

 14 Consider the CN C 2 in Figure5b. The marking m = {s 1 , s 7 , s 8 , s 9 } is reachable because of the following firing sequence:m [{b, d} {s 0 , s 1 , s 4 , s 7 , s 9 } [{c} mThen, it holds that • m = {b, c, d} is a configuration of C 2 (where Conf CN (C 2 ) is defined in Example 13). Conversely, take X = {b, c, d} ∈ Conf CN (C 2 ), and note that • X = {s 0 , s 2 , s 3 , s 4 , s 5 } and X • = {s 7 , s 8 , s 9 }. Then, we have that ({a, c},

•

  S = {( * , e) | e ∈ E} ∪ {(e, * ) | e ∈ E} ∪ {({e, e }, #) | e # e }, • F = {(s, e) | s = ( * , e) ∨ (s = (W, #) ∧ e ∈ W )} ∪ {(e, s) | s = (e, * )}, • I = {(s, e) | s = ( * , e ) ∧ e < e}, and • m = {( * , e) | e ∈ E} ∪ {({e, e }, #) | e # e }.

Example 16 :

 16 Consider the pCN C 1 of Example 12. Note that, b c holds because • c ∩ • b = ∅ and a#b (also b#a) because • a ∩ • b = ∅. Hence, Q(C 1 ) = ({a, b, c, d}, {(b, c)}, {(a, b), (b, a)}). The PES associated with the CN C 2 of Example 12 is Q(C 2 ) = ({a, b, c, d}, {(b, c)}, {(a, b), (b, a), (a, c), (b, c))} which is actually a PES because conflicts are hereditary. Proposition 4: Let C be a pCN. Then Q(C) is a pPES and Conf pPES (Q(C)) = Conf pCN (C).

  ) I = I ∪ {(( * , e), (u, r)) | e ≺ u} ∪ {((e, * ), (u, r)) | e u}.

Fig. 7 :Fig. 8 :

 78 Fig. 7: A simple rCN

(Fig. 9 :

 9 Fig. 9: A r (P 3 )

Fig. 10 :

 10 Fig. 10: A conflict-saturated net

Definition 20 :

 20 An occurrence net (ON) O = B, E, F, c is an acyclic, safe net satisfying the following restrictions: • ∀b ∈ B. • b is either empty or a singleton, and ∀b ∈ c. • b = ∅, • ∀b ∈ B. ∃b ∈ c such that b ≤ O b, • for all e ∈ E the set {e ∈ E | e ≤ O e} is finite, and • # is an irreflexive and symmetric relation defined as follows: e # 0 e iff e, e ∈ E, e = e and • e ∩ • e = ∅, x # x iff ∃y, y ∈ E such that y # 0 y and y ≤ O x and y ≤ O x . Each condition b in an ON represents the occurrence of a token. Hence, b either belongs to the initial marking c or is produced by the unique event in • b. The flow relation is interpreted as the causality relation among the elements of the net; for this reason we say that x causally depends on y iff y ≤ O x. Observe that ≤ O ∩(E × E) is a partial order and # is inherited along ≤ O ; hence, e # e ≤ O e implies e # e . Proposition 8: Let O = B, E, F, c be an occurrence net. Then, O is a single execution net.

•

  S = {( * , e) | e ∈ E} ∪ {(e, * ) | e ∈ E} ∪ {({e, e }, #) | e # e }; • F = {(s, e) | s = ( * , e) ∨ (s = (W, #) ∧ e ∈ W )}; ∪ {(e, s) | s = (e, * )}; • I = {(s, e) | s = ( * , e ) ∧ e < C e}; and • m : S → N is such that m(s) = 0 if s = (e, * ) and m(s) = 1 otherwise, The construction resembles the one from PESes to CNs:

Fig. 11 :

 11 Fig. 11: An occurrence net as a causal net Proposition 9: Let O be an occurrence net. Then O(O) is a CN and O ≡ O(O).We stress that O(O) is conflict-saturated for any ON O.

Fig. 12 :

 12 Fig. 12: A causal net as an occurrence net By combining Proposition 9 and Proposition 10 we obtain the following result. Theorem 5: Let C be a causal net. Then C = O(Z(C)). Let O be an occurrence net. Then O ≡ Z(O(O)).Despite we can directly obtain a PES from an ON (and vice versa)[START_REF] Winskel | Event Structures[END_REF], the mappings introduced in Sections IV-A and IV-B give us an alternative procedure that relies on the intermediate representation of PESes in terms of CNs, as stated below. Theorem 6: Let P be a PES. Then Z(A(P)) is an ON and Conf PES (P) = Conf ON (Z(A(P))). Let O be an ON. Then Q(O(O)) is a PES and Conf ON (O) = Conf PES (Q(O(O))).

Theorem 6 :

 6 Let P be a PES. Then Z(A(P)) is an ON and Conf PES (P) = Conf ON (Z(A(P))). Let O be an ON. Then Q(O(O)) is a PES and Conf ON (O) = Conf PES (Q(O(O))).

Fig. 13 :

 13 Fig. 13: Recap of results. Solid arrows represent known results/works in the literature while dashed arrows stand for results in this paper. Double-headed arrows are used for correspondences while curly tailed arrows are for inclusions and reversible extensions.

  they have the same set of configurations, i.e., Conf rPES (P 1 ) = Conf rPES (P 2 ). Example 7: Consider the rPES P 1 introduced in Example 4. Its set of configurations Conf rPES (P 1 ) is {∅, {a}, {b}, {d}, {a, d}, {b, d}, {b, c}, {b, c, d}}

	(the corresponding sequences of transitions are shown in
	Example 6)

  We write St(N ) for the set of all states of N . We say that N 1 and N 2 are equivalent, written N 1 ≡ N 2 , if they have the same set of states, i.e., St(N 1 ) = St(N 2 ). , s 3 , s 4 }, {s 1 , s 2 , s 6 }, {s 4 , s 5 }, {s 2 , s 4 , s 6 }} while it set of states is St(N 1 ) = {∅, {a}, {c}, {a, b}, {a, c}}.An IPT N is safe if each reachable marking is a set, i.e., ∀m ∈ M N .m = [[m]].Hereafter, we will consider only safe

	Example	11:	The	set	of	reachable	mark-
	ings of the IPT in Example 9 is M N1	=
	{m, {s 2

IPT.

Acknowledgements: We thank the anonymous reviewers for their careful reading of our paper and their useful comments.


Melania Figueroa
email: melania.figueroa@csiro.au

Diana Ortiz

Eva C Henningsen

Jeffery L Dangl

Jonathan D G Jones

Pennington Hg

Tactics of host manipulation by intracellular effectors from plant pathogenic fungi

Keywords: Effector, Fungi, Host, Recognition, Immunity, Plant. Abbreviations Avr, avirulence, bZIP, basic leucine zipper, DON, deoxynivalenol, EAR, ethylene-responsive element binding factor-associated amphiphilic repression, EBE, effector binding element, ER, endoplasmic reticulum, ERF, ethylene response factor, ETI, effector-triggered immunity, HMA, heavy metal associated, HR, hypersensitive response, ID, integrated domain

Fungal pathogens can secrete hundreds of effectors, some of which are known to promote host susceptibility. This biological complexity, together with the lack of genetic tools in some fungi, presents a substantial challenge to develop a broad picture of the mechanisms these pathogens use for host manipulation. Nevertheless, recent advances in understanding individual effector functions are beginning to flesh out our view of fungal pathogenesis. This review discusses some of the latest findings that illustrate how effectors from diverse species use similar strategies to modulate plant physiology to their advantage. We also summarize recent breakthroughs in the identification of effectors from challenging systems, like obligate biotrophs, and emerging concepts such as the 'iceberg model' to explain how the activation of plant immunity can be turned off by effectors with suppressive activity.

Introduction

Pathogens secrete effector proteins to subvert plant immune responses and colonize the host [START_REF] Dodds | Plant immunity: towards an integrated view of plant-pathogen interactions[END_REF]. The role of these molecules in plantemicrobial compatibility has been demonstrated in diverse pathosystems (biotrophic, necrotrophic, and hemibiotrophic), including those responsible for serious fungal crop diseases [START_REF] Presti | Fungal effectors and plant susceptibility[END_REF][START_REF] Dean | The Top 10 fungal pathogens in molecular plant pathology[END_REF]. Pathogen effectors were initially recognized as being the targets of recognition in plant immunity, but the field of effector biology has since provided many important insights into the broad range of mechanisms that plants use to resist disease and how pathogens overcome plant defense. One layer of plant immunity, pathogen-associated molecular pattern (PAMP)-triggered immunity, involves pathogen recognition by plasma membranee associated proteins known as pattern recognition receptors and is a common target of effectors to suppress host defense [START_REF] Dodds | Plant immunity: towards an integrated view of plant-pathogen interactions[END_REF][START_REF] Jones | The plant immune system[END_REF][START_REF] Couto | Regulation of pattern recognition receptor signalling in plants[END_REF]. However, effector recognition occurs via intracellular nucleotide-binding site leucinerich repeat immunoreceptors (NLRs) or plasma membraneelocalized receptors (similar to pattern recognition receptors), which is the basis of effector-triggered immunity as a second layer of plant immunity [START_REF] Thomma | Of PAMPs and effectors: the blurred PTI-ETI dichotomy[END_REF][START_REF] Van Der Burgh | Plant immunity: thinking outside and inside the box[END_REF].

Bacterial effectors have been studied for decades, and much detail is known about their biological functions [START_REF] Xin | Pseudomonas syringae: what it takes to be a pathogen[END_REF][START_REF] Toruño | Plant-pathogen effectors: cellular probes interfering with plant defenses in spatial and temporal manners[END_REF]. Work on oomycete effectors has expanded greatly in recent years and has been thoroughly reviewed previously [10e12]. However, our understanding of fungal effector repertoires, particularly from obligate biotrophs, is less extensive. Here, we review recent findings on subcellular localization of intracellular proteinaceous fungal effectors and their modes of action to manipulate host machinery. We highlight parallels and contrasts with bacterial effectors, emerging concepts in the field, as well as recent breakthroughs in the identification of effectors from obligate biotrophic fungi, which has been a significant research bottleneck. In acknowledgement of exceptions to the standard effector-triggered immunity/PAMP-triggered immunity dichotomy [START_REF] Thomma | Of PAMPs and effectors: the blurred PTI-ETI dichotomy[END_REF][START_REF] Van Der Burgh | Plant immunity: thinking outside and inside the box[END_REF][START_REF] Saintenac | Wheat receptor-kinase-like protein Stb6 controls gene-for-gene resistance to fungal pathogen Zymoseptoria tritici[END_REF], diagrams included in this review adopt the 'spatial invasion model' to portray plant immunity as a process controlled by cell surface and intracellular immunoreceptors [START_REF] Cook | Understanding plant immunity as a surveillance system to detect invasion[END_REF][START_REF] Kanyuka | Cell surface immune receptors: the guardians of the plant's extracellular spaces[END_REF].

Subcellular targeting of intracellular proteinaceous fungal effectors

Intracellular proteinaceous effectors exert their function in the cytosol or travel to other subcellular compartments. Many pathogenic fungi secrete hundreds of effectors [START_REF] Thordal-Christensen | Why did filamentous plant pathogens evolve the potential to secrete hundreds of effectors to enable disease?[END_REF], which have evolved to target key host survival processes and diverse plant cell compartments like those in bacterial systems. A significant advance in the field is the use of prediction tools for protein secretion and subcellular localization such as EffectorP and LOCALIZER [START_REF] Sperschneider | LOCALIZER: subcellular localization prediction of both plant and effector proteins in the plant cell[END_REF][START_REF] Sperschneider | Improved prediction of fungal effector proteins from secretomes with EffectorP 2.0[END_REF], which can guide experimental analyses (e.g. fluorescence microscopy, heterologous expression systems). Results from this work show the numerous cellular compartments (i.e. nucleus, the Golgi apparatus, chloroplasts, mitochondria, etc.) that effectors target [START_REF] He | All roads lead to susceptibility: the many modes of action of fungal and oomycete intracellular effectors[END_REF][START_REF] Robin | Subcellular localization screening of Colletotrichum higginsianum effector candidates identifies fungal proteins targeted to plant peroxisomes, golgi bodies, and microtubules[END_REF][START_REF] Lorrain | Show me the way: rust effector targets in heterologous plant systems[END_REF] (Table 1, Figure 1). Nevertheless, linking effector localization and function is a challenging task because of the genetic intractability of some fungi or the subtlety, or even absence, of phenotypes in effector mutants resulting from functional redundancy or minor effects [START_REF] Selin | Elucidating the role of effectors in plant-fungal interactions: progress and challenges[END_REF].

Chloroplasts [START_REF] Petre | Candidate effector proteins of the rust pathogen Melampsora larici-populina target diverse plant cell compartments[END_REF] determined that the three secreted proteins (CTP1, CTP2, and CTP3) from the poplar rust fungus (Melampsora larici-populina) accumulate in the chloroplast by exploiting cellular sorting processes. Their trafficking depends on the in planta cleavage of an Nterminal signal sequence which mimics plant chloroplast targeting sequences. Similarly, targeting-sequence mimicry has been found in Puccinia graminis f. sp. tritici (wheat stem rust) effectors that show chloroplast localization [START_REF] Sperschneider | LOCALIZER: subcellular localization prediction of both plant and effector proteins in the plant cell[END_REF]. Further evidence comes from Puccinia striiformis f. sp. tritici (wheat stripe rust fungus); the effector protein Pst_12806 contains a chloroplast transit peptide and localizes to the chloroplast, where it perturbs photosynthesis and basal immunity [START_REF] Xu | An effector protein of the wheat stripe rust fungus targets chloroplasts and suppresses chloroplast function[END_REF]. In some cases, effector localization and phenotype changes occur in different organelles.

Manipulation through subversion of host machinery

Fungal effectors, as well as those from oomycetes, often subvert host machinery/processes by binding to host targets [START_REF] He | All roads lead to susceptibility: the many modes of action of fungal and oomycete intracellular effectors[END_REF], rather than modifying the target via an intrinsic enzymatic activity, as commonly observed for bacterial effectors [START_REF] Xin | Pseudomonas syringae: what it takes to be a pathogen[END_REF]31]. For instance, Jiang et al.

[32] showed that the effector protein Osp24 from Fusarium graminearum physically associates with TaSnR-K1a, a wheat homolog of the Arabidopsis thaliana SNF1related kinase (SnRK1). SnRK1 plays a pivotal regulatory role in plant metabolism, growth, and immunity and is regulated by a Skp1eCullineF-box ubiquitin ligase complex and 26S proteasome [33,34]. In wheat, TaSnRK1a contributes to resistance to F. graminearum by an unknown mechanism and Osp24 promotes proteasomal degradation of TaSnRK1a during fungal infection [32]. In an interesting case of arms-race evolution, another wheat protein TaFROG is induced by detection of the Fusarium toxin deoxynivalenol and competes with Osp24 for binding to TaSnRK1a to prevent its degradation and maintain resistance. 1.

Phytohormone signaling processes are also manipulated by fungal effectors. The Ustilago maydis effector Jsi1 targets jasmonate/ethylene signaling by interaction with members of the TOPLESS/TOPLESSrelated corepressor family. This activates jasmonate/ ethylene signaling by transcriptional reprogramming of genes related to the ethylene response factor branch [35]. In another case of molecular mimicry, Jsi1 contains a DLNxxP type EAR motif, similar to those conserved in plant ethylene response factor transcription factors that naturally activate this pathway [36]. Similarly, the candidate effector MLP124017 from M. larici-populina interacts with the TOPLESS-related protein 4 (PopTPR4) from poplar and Nicotiana benthamiana [START_REF] Petre | Candidate effector proteins of the rust pathogen Melampsora larici-populina target diverse plant cell compartments[END_REF]37]; however, the functional consequence of this interaction has not been determined.

Fungi also target host plant signaling cascades, as evidenced by AvrLm1 from Leptosphaeria maculans, which like some bacterial and oomycete effectors, targets the mitogen-activated protein kinase (MAPK) signaling cascade to modulate plant immunity [38]. AvrLm1 interacts with the Brassica napus MAPK 9, which leads to accumulation and phosphorylation of MAPK9. This results in cell death induction which may support the pathogen's transition from a biotrophic to necrotrophic phase. Another example of subversion of host machinery is given by the effector VdSCP41 from Verticillium dahliae, which interferes with the function of the Arabidopsis transcription factors CBP60g and SARD1 and cotton GhCBP60b, which serve as regulators of immunity [39]. Some effectors directly bind to DNA and use the host transcriptional machinery to alter gene expression and defense responses. Recently, Kim et al.

[40] characterized two M. oryzae effector proteins, MoHTR1 and MoHTR2, which are translocated into the nucleus, where they bind to so-called effector binding elements of genes related to plant immunity regulation. Changes in the transcriptional profile caused by MoHTR1 and MoHTR2 impact how rice responds to additional pathogens. Transgenic rice lines expressing MoHTR1 or MoHTR2 display increased susceptibility to hemibiotrophic pathogens M. oryzae and Xanthomonas oryzae pv. oryzae, but show enhanced resistance to Cochliobolus miyabeanus, a necrotrophic pathogen (Figure 2). This highlights an interesting observation that host manipulation by the effector repertoire of one pathogen can modify the outcomes of other plante microbe interactions.

Emerging concepts and unanswered questions for intracellular fungal effectors

The genomic era has revealed not only that many fungi harbor hundreds of effector proteins, but also that plants possess large sets of immunity receptors [START_REF] Presti | Fungal effectors and plant susceptibility[END_REF]41,42]. Yet, it is intriguing that genetic studies attribute incompatibility between plants and adapted pathogens to only a few receptors and corresponding Avr proteins (interaction units). The iceberg model proposed by Thordal-Christensen [START_REF] Thordal-Christensen | A holistic view on plant effectortriggered immunity presented as an iceberg model[END_REF] seeks to explain this observation as resulting from one effector suppressing the activation of plant immunity mediated by the recognition of another effector (Figure 3). Such interference leads to silent interaction units as the invisible base of the iceberg, whereas we are only able to detect those units that lead to disease resistance at the tip of the iceberg. Consistent with this model, the Avr1 effector from Fusarium oxysporum suppresses resistance responses induced by the NLR proteins I-2 and I-3, while activating resistance mediated by I and I-1 in tomato plants [START_REF] Houterman | Suppression of plant resistance gene-based immunity by a fungal effector[END_REF]. Similarly, the SvrPm3 a1/f1 effector protein from Blumeria graminis f. sp. tritici has been shown to suppress cell death triggered on recognition of AvrPm3 a2/f2 by the resistance protein Pm3 in N. benthamiana and in wheat [33,45]. Cell death suppression activity may also be part of the mechanism of action of effectors deployed by rust fungi [34,46,[START_REF] Ramachandran | Effectors from wheat rust fungi suppress multiple plant defense responses[END_REF]. Functional redundancy of effectors [48e50] can also explain why we only seem to detect a few interaction units.

Individual fungal effectors may have more than one function by targeting different host proteins. For instance, AvrPiz-t from M. oryzae targets two ubiquitin E3 ligases, a Kþ transporter, a basic leucine zipper transcription factor, and a nucleoporin protein Nup98 in rice [51e55]. Conversely, multiple effectors may display common host targets. Variants of AvrPik bind and stabilize rice proteins containing heavy metale associated (HMA) domains, which act as susceptibility factors to promote disease [START_REF] Oikawa | The blast pathogen effector AVR-Pik binds and stabilizes rice heavy metal-associated (HMA) proteins to co-opt their function in immunity[END_REF][START_REF] Maidment | biochemical and structural basis of the interaction between AVR-Pik, an ffector in Magnapothe oryzae and OsHIPP19, a puattive virulence target in rice. AVR-Pik interacts with HMA domain of Pik-1; however, variants[END_REF][START_REF] Kanzaki | Arms race co-evolution of Magnaporthe oryzae AVR-Pik and rice Pik genes driven by their physical interactions[END_REF]. The HMA domain is also present as an integrated domain in some NLRs, including Pik, where it allows immune recognition of AvrePik [59e61]. Two other M. oryzae effectors, AVRePia and AVR1eCO39, are also recognized by their binding to integrated HMA domains in NLRs [START_REF] Cesari | The rice resistance protein pair RGA4/RGA5 recognizes the Magnaporthe oryzae effectors AVR-Pia and AVR1-CO39 by direct binding[END_REF][START_REF] Ortiz | Recognition of the Magnaporthe oryzae effector AVR-Pia by the decoy domain of the rice NLR immune receptor RGA5[END_REF][START_REF] Guo | Specific recognition of two MAX effectors by integrated HMA domains in plant immune receptors involves distinct binding surfaces[END_REF]. This suggests that these effectors have all evolved the ability to target host proteins containing HMA domains and consequently driven evolution of NLR receptors with HMA-like integrated domains. These three effectors, as well as AvrPiz-t and the apoplastic effector PtrToxB from P. tritici repentis [START_REF] Nyarko | Solution NMR structures of Pyrenophora tritici-repentis ToxB and its inactive homolog reveal potential determinants of toxin activity[END_REF] are all structurally related, being members of the MAX (Magnaporthe Avrs and ToxB-like effectors) effector family [START_REF] De Guillen | Structure analysis uncovers a highly diverse but structurally conserved effector family in phytopathogenic fungi[END_REF]. This indicates that effectors with common structural scaffolds can evolve to quite different functions, which complicates the application of structural information to predict effector function. Likewise, many powdery mildew effectors are predicted to share a common RNase-like fold [START_REF] Praz | AvrPm2 encodes an RNase-like avirulence effector which is conserved in the two different specialized forms of wheat and rye powdery mildew fungus[END_REF][START_REF] Pedersen | Structure and evolution of barley powdery mildew effector candidates[END_REF][START_REF] Pliego | Hostinduced gene silencing in barley powdery mildew reveals a class of ribonuclease-like effectors[END_REF]69], which may serve as a structural scaffold to support multiple functions.

The existence of 'core' effectors that are conserved across pathogens is an intriguing topic [START_REF] Lanver | Ustilago maydis effectors and their impact on virulence[END_REF]70,71]. Although most effectors characterized to date are pathogen specific, it would be interesting to identify the functions of more broadly conserved effectors, which may represent indispensable pathogenicity functions. The fungal effector necrosis-inducing secreted protein 1, which is widely conserved in filamentous fungi, targets BAK1 and BIK and interferes with signaling derived from cell surface pathogen recognition [72]. If core effectors often target basal immunity like in the case of necrosis-inducing secreted protein 1, these may also alter outcomes of other plantemicrobial interactions.

The inability to culture and transform obligate biotrophic fungi, such as rusts and powdery mildews, has limited the isolation and characterization of effectors in these fungi. However, advances in genomic and genetic resources have led to the identification of several Avr effector genes in wheat stem rust (P. graminis f. sp. tritici) [34,73,74,75,76,77,78] and wheat and barley powdery mildews (B. graminis f. sp. tritici and B. graminis f. sp. hordei, respectively) [33,45,78,79] (Table 1). Other exciting progress in obligate biotrophic fungi includes the identification of Avr effector candidates in Puccinia coronata f. sp. avenae [80], Uromyces appendiculatus [START_REF] Qi | Candidate effectors from Uromyces appendiculatus, the causal agent of rust on common bean, can Be discriminated based on suppression of immune responses[END_REF], and Hemileia vastatrix [START_REF] Maia | The Hemileia vastatrix effector Hv EC-016 suppresses bacterial blight symptoms in coffee genotypes with the SH 1 rust resistance gene[END_REF]. These breakthroughs open new research opportunities to understand effector recognition and function in these systems. For instance, functional characterization of the ribonuclease-like effector CSEP0064/BEC1054 from B. graminis f. sp. hordei [69] has revealed inhibition of ribosome-inactivating proteins as a mechanism to prevent cell death and promote susceptibility. An interesting observation is that resistance to obligate biotrophic fungal pathogens generally relies on direct effector recognition by NLRs (receptor ligand model), rather than indirect recognition commonly seen in bacterial resistance (Figure 3) [START_REF] Figueroa | Evolution of virulence in rust fungi -multiple solutions to one problem[END_REF][START_REF] Saur | Recognition and defence of plantinfecting fungal pathogens[END_REF]. The mechanisms underlying translocation of fungal effectors into the plant cell remain unknown [START_REF] Presti | how filamentous plant pathogen effectors are translocated to host cells[END_REF]. The sequence diversity of these molecules and lack of conserved motifs present challenges to address this question.

Concluding statements

During the 2019 International Society Molecular Plante Microbe Interactions conference, our scientific community selected "Why do some pathogens need so many effectors when others need a few?" as one of the top 10 unanswered questions in the field [START_REF] Harris | What are the top 10 unanswered questions in molecular plant-microbe interactions[END_REF]. This question is particularly relevant to fungi, which often contain large effector repertoires compared with bacteria. The more complex lifestyle and evolutionary history of pathogenic fungi may mean that they need to target additional host processes to support successful infection. Their larger genome size may also permit the evolution of an effector repertoire with substantial redundancy to enhance the robustness of pathogenicity mechanisms. The answer to this question may also require looking beyond the individual functions of effectors to consider how their combinatorial effects enhance disease susceptibility.

32

. Jiang C, Hei R, Yang Y, Zhang S, Wang Q, Wang W, Zhang Q, Yan M, Zhu G, Huang P: An orphan protein of Fusarium graminearum modulates host immunity by mediating proteasomal degradation of TaSnRK1a. Nat Commun 2020, 11:1-13. This paper illustrates the tug-of-war between the effector Osp24 from F. graminearum and TaFROG to bind to TaSnRK1a in wheat to induce or prevent ubiquitin 26S-proteasome-mediated degradation of TaSnRK1a, respectively. TaSnRK1a plays a role in pathogen resistance and therefore targeting this protein by a cytoplasmic effector from F. graminearum is advantageous for fungal colonization. F. graminearum produces mycotoxins such as deoxynivalenol (DON) during infection. In presence of DON, TaFROG competes for binding to TaSnRK1a at the same site than Osp24, which stabilizes the protein to prevent ubiquitin 26S-proteasome-mediated degradation.

Figure 1 Examples

 1 Figure 1

Figure 2 Manipulation

 2 Figure 2

Figure 3 Effectors

 3 Figure 3

.

  Xu G, Zhong X, Shi Y, Liu Z, Jiang N, Liu J, Ding B, Li Z, Kang H, Ning Y: A fungal effector targets a heat shock-dynamin protein complex to modulate mitochondrial dynamics and reduce plant immunity. Sci Adv 2020, 6, eabb7719. The authors demonstrate a functional link between mithocondrial dynamics and innate immunity. The M. oryzae effector protein MoCDIP4 interferes with the function of two rice proteins, OsDjA9 and the dynamin related protein OsDRP1E, which are involved in the regulation of mithochondrial activity. The interaction of OsDjA9 and OsDRP1E leads to the degradation of OsDRP1E. The binding of MoCDIP4 to OsDjA9 results in the accumulation of OsDRP1E leading to increased rice susceptibility to M. oryzae. 31. Galán JE: Common themes in the design and function of bacterial effectors. Cell Host Microbe 2009, 5:571-579.

  33. Bourras S, McNally KE, Ben-David R, Parlange F, Roffler S, Praz CR, Oberhaensli S, Menardo F, Stirnweis D, Frenkel Z, et al.: Multiple avirulence loci and allele-specific effector recognition control the Pm3 race-specific resistance of wheat to powdery mildew. Plant Cell 2015, 27:2991-3012. 34 . Chen J, Upadhyaya NM, Ortiz D, Sperschneider J, Li F, Bouton C, Breen S, Dong C, Xu B, Zhang X, et al.: Loss of AvrSr50 by somatic exchange in stem rust leads to virulence for Sr50 resistance in wheat. Science 2017, 358:1607-1610. Together with Salcedo et al. [75] the authors report the cloning of the first Avr effector from a cereal rust fungus and demonstrate that direct recognition of Avr-R pairs occur in these organisms. 35 . Darino M, Chia KS, Marques J, Aleksza D, Soto Jimenez LM, Saado I, Uhse S, Borg M, Betz R, Bindics J, et al.: Ustilago maydis effector Jsi1 interacts with Topless corepressor, hijacking plant JA/ET signaling. New Phytol 2021, 229: 3393-3407. This paper describes how the U. maydis effector Jsi1 induces the ethylene response factor branch of the jasmonate/ethylene signaling pathway through direct interaction with Topless/Topless related (TPL/ TPR) family proteins. Jsi localizes to the nucleus and manipulation of the TPL/TPR hub results in increased susceptibility to a biotrophic pathogen. 36. Yang J, Liu Y, Yan H, Tian T, You Q, Zhang L, Xu W, Su Z: PlantEAR: Functional Analysis Platform for Plant EAR Motif-Containing Proteins, 9; 2018. 37. de Guillen K, Lorrain C, Tsan P, Barthe P, Petre B, Saveleva N, Rouhier N, Duplessis S, Padilla A, Hecker A: Structural genomics applied to the rust fungus Melampsora larici-populina reveals two candidate effector proteins adopting cystine knot and NTF2-like protein folds. Sci Rep 2019, 9:18084. 38. Ma L, Djavaheri M, Wang H, Larkan NJ, Haddadi P, Beynon E, Gropp G, Borhan MH: Leptosphaeria maculans effector protein AvrLm1 modulates plant immunity by enhancing MAP kinase 9 phosphorylation. iScience 2018, 3:177-191. 39. Qin J, Wang K, Sun L, Xing H, Wang S, Li L, Chen S, Guo HS, Zhang J: The plant-specific transcription factors CBP60g and SARD1 are targeted by a Verticillium secretory protein VdSCP41 to modulate immunity. Elife 2018:7. 40 . Kim S, Kim CY, Park SY, Kim KT, Jeon J, Chung H, Choi G, Kwon S, Choi J, Jeon J, et al.: Two nuclear effectors of the rice blast fungus modulate host immunity via transcriptional reprogramming. Nat Commun 2020, 11:5845. In this paper the authors identified two nuclear M. oryzae effectors, MoHTR1 and MoHTR2 that function as transcriptional repressors to reprogram the transcription of rice genes associated with immunity. To regulate rice gene expression, MoHTR1 and MoHTR2 bind the promotor of their gene targets, often reducing expression of those genes. Interestingly, transgenic rice plants individually expressing MoHTR1 or MoHTR2 show contrasting responses to pathogen infection. They display an increased susceptibility to the M. oryzae and X. oryzae, both hemibiotrophic pathogens, and increased resistance to a necrotrophic pathogen, C. miyabeanus. 41. Baggs E, Dagdas G, Krasileva KV: NLR diversity, helpers and integrated domains: making sense of the NLR IDentity. Curr Opin Plant Biol 2017, 38:59-67. 42. Sánchez-Vallet A, Fouché S, Fudal I, Hartmann FE, Soyer JL, Tellier A, Croll D: The genome biology of effector gene evolution in filamentous plant pathogens. Annu Rev Phytopathol 2018, 56:21-40.

Table 1

 1 Summary of fugal effectors mentioned in this review to illustrate their diverse subcellular localization and function if applicable.

	Effector	Function	In planta subcellular	Species	Lifestyle	Disease name	Host	Reference
			localization
	Avra7, Avra9,	Unknown	Unknown	Blumeria graminis f. sp.	Biotroph	Powdery mildew	Barley	[79]
	Avra10, and			hordei
	Avra22
	CSEP0064/	RNase-like protein that binds to	Cytoplasm and nucleus B. graminis f. sp. hordei Biotroph	Powdery mildew	Barley	[69]
	BEC1054	nucleic acids and prevents
		degradation of host ribosomal
		RNA induced by ribosome-
		inactivating proteins
	SvrPm3al/f1	Suppresses recognition of	Unknown	B. graminis f. sp. tritici	Biotroph	Powdery mildew	Wheat	[33,45]
		AvrPm3a2/f2 mediated by the
		Pm3 wheat resistant gene
	ChEC89	Unknown	Peroxisome	Colletotrichum	Hemibiotroph Anthracnose	Cruciferous plants	[19]
				higginsianum
	ChEC21	Unknown	Golgi apparatus	C. higginsianum	Hemibiotroph Anthracnose	Cruciferous plants	[19]
	NIS1	Disrupts basal immunity by binding	Cytosol	Colletotrichum	Hemibiotroph Anthracnose and rice	Cucumber, cruciferous	[72CC]
		to BAK1 and BIK1		orbiculare		blast	plants, rice, and so on
				C. higginsianum
				Magnaporthe oryzae
	Avr1(Six4)	Suppression of I-2-and I-	Unknown	Fusarium oxysporum	Hemibiotroph Fusarium wilt, foot, root,	Tomato, cotton, banana,	[44]
		3-mediated disease resistance				or bulb rot	melon
	Osp24	Induction of proteasome-mediated	Cytosol	F. graminearum	Hemibiotroph Fusarium head blight	Wheat and barley	[32CC]
		degradation of its host target
	HvEC-016	Unknown	Unknown	Hemileia vastatrix	Biotroph	Coffee leaf rust	Coffee	[82]
	AvrLm1	Alterations to MAPK signaling	Cytosol	Leptosphaeria maculans Hemibiotroph Black leg	Canola	[38]
	MoCDIP4	Disruption of mitochondrial	Endoplasmic reticulum M. oryzae	Hemibiotroph Rice blast	Rice	[30CC]
		dynamics
	MoHTR1 and	Transcriptional reprogramming of	Nucleus	M. oryzae	Hemibiotroph Rice blast	Rice	[40CC]
	MoHTR2	genes related to plant immunity
	AvrPiz-t	Inhibition of RING E3 ubiquitin	Cytosol	M. oryzae	Hemibiotroph Rice blast	Rice	[51-54]
		ligases APIP6 and APIP10,
		modulation of a K+ channel,
		targeting of Nup08 (the homolog
		of APIP12) and preventing
		accumulation of PR transcripts,
		and suppression of activity of the
		bZIP-type transcription factor
		APIP5
	AVR-Pia	Unknown	Cytosol	M. oryzae	Hemibiotroph Rice blast	Rice	[60,62]
	CTP1	Unknown	Chloroplast,	Melampsora larici-	Biotroph	Poplar leaf rust	Poplar	[28]
			mitochondria	populina
	CTP2, CTP3	Unknown	Chloroplast,	M. larici-populina	Biotroph	Poplar leaf rust	Poplar	[28]

Current Opinion in Plant Biology 2021, 62:102054 www.sciencedirect.com

Current Opinion in Plant Biology 2021, 62:102054 www.sciencedirect.com

Acknowledgements

Research led by M.F. is supported by the 2Blades Foundation, United States. E.C.H. is supported by a scholarship from the College of Food, Agricultural and Natural Resource Sciences at the University of Minnesota, United States. D.O. is supported by LEAP-Agri (A Long-term EUeAfrica research and innovation Partnership on food and nutrition security and sustainable Agriculture), Cassandra ANR-18-LEAP-0004-03 project. The authors thank Dr. Louise Thatcher for feedback on the manuscript. The authors apologize to their colleagues whose work was not cited because of space limitations.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this article.

. Bourras S, Kunz L, Xue M, Praz CR, Muller MC, Kalin C, Schlafli M, Ackermann P, Fluckiger S, Parlange F, et al.: The AvrPm3-Pm3 effector-NLR interactions control both racespecific resistance and host-specificity of cereal mildews on wheat. Nat Commun 2019, 10:2292. This article demonstrates that the Pm3 multiallelic race-specific resistance in wheat against Blumeria graminis f. sp. tritici involves an allelespecific Avr effector, a R gene allele, and a pathogen-encoded suppressor of avirulence. The authors cloned the effector gene AvrPm3 a2/ f2 , which is recognized by Pm3a and Pm3f alleles, and show that gene expression levels play a role in plant pathogen incompatibility.

46

. Qi and Avr a22 in Blumeria graminis f. sp. hordei by transcriptome-wide association studies. They also demonstrated that these effectors are directly recognized by their corresponding allelic MLA7, MLA9, MLA10 and MLA22 immunoreceptors. These findings support the idea that unlike the indirect NLR mediated recognition often observed for bacterial effectors, MLA like receptors have evolved the ability to directly recognize fungal effectors. This likely explains the MLA functional diversification observed in the host population. e1009291. The authors report a dramatic shift in population virulence profiles of the oat crown rust fungus between 1990 and 2015, which is associated with substantial genetic differentiation between the two populations. The authors identify seven Avr loci associated with virulence phenotypes on fifteen R genes, with most loci containing a single candidate Avr gene. A selective sweep at a single Avr locus corresponding to six R genes is associated with a complete shift to virulence on these R genes in the 2015 population. This research piece represents the first application of a genome-wide association study to uncover Avr effectors in a rust fungus.