In this paper the correspondence between safe Petri nets and event structures, due to Nielsen, Plotkin and Winskel, is extended to arbitrary nets without self-loops, under the collective token interpretation. To this end we propose a more general form of event structure, matching the expressive power of such nets. These new event structures and nets are connected by relating both notions with configuration structures, which can be regarded as representations of either event structures or nets that capture their behaviour in terms of action occurrences and the causal relationships between them, but abstract from any auxiliary structure. A configuration structure can also be considered logically, as a class of propositional models, or-equivalentlyas a propositional theory in disjunctive normal from. Converting this theory to conjunctive normal form is the key idea in the translation of such a structure into a net. For a variety of classes of event structures we characterise the associated classes of configuration structures in terms of their closure properties, as well as in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated Petri nets. The aim of this paper is to connect several models of concurrency, by providing behaviour preserving translations between them. The present paper generalises the correspondence between safe Petri nets and configuration structures to (possibly unsafe) nets without self-loops (the pure nets). For this purpose we use 1 a more general kind of configuration structure than in [11] , the set systems. These have an attractive alternative presentation as propositional theories [29] , which is exploited in their translation to nets. We also generalise the event structures of [34] , so that, again, our configuration structures arise as their families of configurations. The connection between configuration structures and Scott domains is generalised in Van Glabbeek [8], who proposes transition systems as alternative presentations of domains; we do not consider these matters further in the present paper. The relationship between configuration structures, infinitary propositional theories, event structures and Petri nets is described in Section 1. We 1-unfold pure nets into pure 1-occurrence nets, which generalise the occurrence nets of [25] , and argue that this 1-unfolding preserves the causal and branching time behaviour of the represented system. This allows us to restrict attention to pure 1-occurrence nets in the rest of the paper. Moreover, we give translations showing that configuration structures, propositional theories and event structures are equivalent up to so-called configuration equivalence (which is defined as being mapped to the same configuration structures) and that, with a slight restriction, all four models are equivalent up to finitary equivalence. Section 2 introduces a computational interpretation of configuration structures, Petri nets and event structures in terms of associated transition relations; restricted to pure Petri nets and pure event structures, these transition relations can be derived from the relevant sets of configurations, but not in general. With that, Section 3 provides definitions of notions of reachable and secured (reachable in the limit) configurations and considers corresponding notions of equivalence by restricting to reachable or secured, and possibly finite, configurations. With the general framework thus provided, Section 4 considers the various brands of event structures introduced by Winskel and his co-workers. They are shown to correspond to natural restrictions on the general notion of event structure, adapting the comparisons, on the one hand, to the original notion of configuration and, on the other hand, to the relevant one from the general theory. These comparisons are summarised in Table 1 . It is then natural to enquire how the event structure restrictions are reflected in corresponding restrictions on configurations structures and so on; this is the subject of Section 5. Sections 5.1 and 5.2 provide such comparisons, summarised in Table 2 , for configuration structures and propositional theories up to configuration equivalence. The restrictions on configuration structures are natural closure properties, and those on propositional theories concern the form of the formulae occurring in an axiomatisation. Section 5.3 does the same, see Table 3 , but now with the comparison based on the secured configurations. Section 5.4 concerns the finitary case, with general comparisons being summarised in Table 4 and the restriction to the finite reachable configurations summarised in Table 5 . Section 5.5 ties in Petri nets, providing corresponding structurally defined subclasses; however we were not successful in doing this in all cases. The main mathematical work is done in Sections 5.1 and 5.2, with the rest of the section adapting this work to the various cases at hand. Section 6 contains a discussion of related work and presents some possibilities for future research. Finally, there is an index for the many technical terms introduced in the course of the paper. The papers [12] and [13] contain extended abstracts of parts of this work, together with additional material. In this section we present the four models of concurrency mentioned in the introduction, and provide translations between them. Definition 1.1 A set system is a pair C = / \ E, C \ / with E a set and C ⊆ P(E) a collection of subsets. When a set system is used to represent a concurrent system, we call it a pure configuration structure, but generally drop the word "pure". (We envision introducing a broader class of configuration structures in the future, matching the expressive power of impure nets.) The elements of E are then called events and the elements of C configurations. An event represents an occurrence of an action the system may perform; a configuration x represents a state of the system, namely the state in which the events in x have occurred. A set system can also be considered from a logical point of view: E is thought of as a collection of propositions and C as the collection of models. Connecting with the computational point of view, we associate with an event the proposition that it has happened. This point of view is due to Pratt [18, 29] . We can now represent a set system by the valid sentences, those holding in all models; these are the laws of C. To make this precise, we choose a language: infinitary propositional logic. Given a set E of (propositional) variables, the formulae over E form the least class including E and closed under ¬ (negation) and (conjunction of sets of formulae). We make free use of other standard connectives such as ⇒, , ⊥, ⊤: they are all definable from ¬ and . As usual, an interpretation of E is just a subset of E and one defines in the standard way when an interpretation makes a formula true. / with E a set of propositional variables and T a class of infinitary propositional formulae over E. iff it is true in all elements of C; the theory associated to C is T (C) : where T (C) denotes the class of formulae valid in C. Equally, given a propositional theory T = is the set of models of T , those interpretations of E making every formula in T true. We say that T axiomatises M(T). A formula ϕ over E is a logical consequence of a theory T if ϕ is true in any model of T; a formula ψ over E implies ϕ iff the latter is a logical consequence of the theory , which is easily seen to be the case iff they have the same logical consequences. Theorem 1 Let C = / \ E, C \ / be a set system. Then T (C) axiomatises C, i.e., M(T (C)) = C. Proof: The single formula X∈C ( X ∧ ¬(E − X)) already constitutes an axiomatisation of C. It is called the disjunctive normal form of T (C). 2 Thus T and M provide a bijective correspondence between set systems and infinitary propositional theories up to logical equivalence. For any two subsets X,Y of E, let the clause X ⇒ Y abbreviate the implication X ⇒ Y ; we say that the elements of X are the antecedents of the clause, and those of Y its consequents. Then for any set system C = / \ E, C \ / , the set of clauses {X ⇒ (E − X) | X ∈ C} constitutes another axiomatisation of C. A theory consisting of a set of clauses is said to be in conjunctive normal form. Definition 1.3 An event structure is a pair E = / \ E, ⊢ \ / with • E a set of events, • ⊢ ⊆ P(E) × P(E), the enabling relation. Like a configuration structure, an event structure describes a concurrent system in which the events represent action occurrences. In previous notions of event structure [34, 35] , one only had singleton enablings: ⊢ ⊆ P(E) × E. Here we generalise ⊢ to a relation between sets of events. As before, the enabling relation places some restrictions on which events can happen when. The idea here is that when X is the set of events that happened so far, an additional set U of events can happen (concurrently) iff every subset of X ∪ U is enabled by a set of events that happened before, i.e., a subset of X. Example 1 Let E = {d, e, f } and the enabling relation be given by ∅ ⊢ X for any X ⊆ E with X = E. In the initial state of the event structure E = / \ E, ⊢ \ / , each of the events d, e and f can happen, and any two of them can happen concurrently. However, there is no way all three events can ever happen, because there is no set of events X with X ⊢ {d, e, f }. This is a case of ternary conflict. Example 2 Let E = {a, b, c} and the enabling relation be given by {c} ⊢ {a, b} and ∅ ⊢ X for any X ⊆ E with X = {a, b}. Initially, each of the events a, b and c can occur, and the events a and c can even happen concurrently. The events a and b, on the other hand, can initially not happen concurrently, for we do not have ∅ ⊢ {a, b}. However, as soon as c occurs, the events a and b can occur in parallel. We say that the conflict between a and b is resolved by the occurrence of c. Example 3 Let E = {d, e} and the enabling relation be given by {d} ⊢ {d, e} and ∅ ⊢ X for any X ⊆ E with X = {d, e}. Initially, d and e can both occur, but not in parallel. After d has happened, e may follow, but when e happens first, d cannot follow. The reason is that we do not have X ⊢ {d, e, } for some X ⊆ {e}. This is a case of asymmetric conflict [22, 26] . In Section 4 we will explain how these event structures generalise the ones of [25, 34, 35] . In those papers the behaviour of an event structure is formalised by associating to it a family of configurations. However, there are several ways to do so (cf. Section 3); here we only consider the simplest variant. In Section 2 we provide a computational interpretation of event structures with the property that the leftclosed configurations of an event structure adequately represent the behaviour of the represented system for the following class of "pure" event structures: Definition 1.5 An event structure is pure if X ⊢ Y only if X ∩ Y = ∅.
The paper REF studies a characterisation of the partial order of configurations for a variety of classes of event structures in terms of axiomatisability of the associated propositional theories.
Configuration Structures, Event Structures and Petri Nets
Theoretical Computer Science 410(41), 2009, pp. 4111-4159
Mathematics Computer Science