You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
David Corfield (Apr 18 2025 at 07:50):Discussions in which I participated brought up the notion of an [[event structure]], something I'd only vaguely known about. Looking into them a little, what a zoo! Mentioned in Pinna's Representing Dependencies in Event Structures are:
Prime event structure (pes); relaxed primed event structure (rpes); flow event structure (fes); shrinking event structure (ses); growing event structure (ges); bundle event structure; dual event structure; asymmetric event structure; circular event structure; inhibitor event structure (ies); event structure with resolvable conflicts (rces); dynamical causality event structure (dces); context-dependent event structure (cdes).
And there are further varieties: reversible, timed, higher-order dynamic-causality, with symmetry, ...
The seminal paper on event structure,
already looked to compare them with other formalisms. So we find correspondences, such as between prime event structures and safe Petri nets. Van Glabbeek and Plotkin carry out more such comparison in Configuration Structures, Event Structures and Petri Nets:
So how do people in the ACT community view event structures today? They seem to present a kind of unfolding of forms of Petri nets. Are there any advantages to that mode of presentation?
John Baez (Apr 18 2025 at 14:22):Maybe a better question is "who in the applied category theory knows about event structures?" I'd never heard of them, but I consider my friend Gordon Plotkin to be an applied category theorist (even if he doesn't), so we could ask him what's going on with event structures. I also feel @Pawel Sobocinski is the kind of guy who might know about event structures: he's worked on Petri nets from a much more computer-scientific point of view than I ever have. (I got into them from chemistry, where they're more often used to set up systems of ODE rather than describe discrete events.)
John Baez (Apr 18 2025 at 14:31):Gordon Plotkin has invented and/or knows about a vast number of simple computer science abstractions that I've never heard of, so whenever I talk to him I hear about a lot of new structures and despair of ever expanding my mental scope enough to incorporate them in my way of thinking.
John Baez (Apr 18 2025 at 14:37):One thing that goes against my physics training is that event structures have a built-in 'arrow of time': there are at most finitely many events that occur before any event, but we can have infinitely many events after any event. This may be very practical if the beginning of time is when you start a program running, and you imagine letting it run indefinitely.
But there are also radical approaches to physics based on [[causal sets]], which are simply posets where for any there are finitely many with . These radical physicists, like Fay Dowker and Rafael Sorkin, want to use causal sets to describe spacetime, with the elements being points of spacetime. I've never seen them impose 'arrow of time' axiom, that only finitely many events occur before any given event, but it sounds like positing a Big Bang. It even reminds me of Aristotle's First Cause, though that could motivate a stronger axiom saying there's a unique event that comes before all others.
Yes, I'm rambling on - these are just some mental associations.
David Corfield (Apr 18 2025 at 15:05):Rambling's fine. :grinning:
Maybe this marks a distinction between communities. Event structures are more likely in a Cambridge (UK) style categorical computer science, whereas ACT has focused on Petri nets.
But to show you how close you've come to them, from the bibliography of A compositional account of motifs, mechanisms, and dynamics in biochemical regulatory networks:
John Baez (Apr 18 2025 at 15:09):So close, and yet so far.
Kevin Carlson (Apr 18 2025 at 22:08):We’ve heard of event structures, but I don’t actually understand them. Maybe @Evan Patterson does.
Evan Patterson (Apr 18 2025 at 22:20):Hey, I recognize that bibliography! I cited the paper "Domain and event structure semantics for Petri nets with read and inhibitor arcs" because the "inhibitor nets" defined there (Def 1) are similar to the "Petri nets with signed links" that we consider. But, as in John's work, we were intererested in applications to chemistry and biology, rather than TCS applications like concurrency. So I confess that I didn't find out what event structures are or how they're related to inhibitor nets. Would be fun to learn about it, though.
John Baez (Apr 19 2025 at 00:42):Yes, I too was interested in the extra structures that paper slapped on Petri nets, rather than the semantics discussed there. Even without understanding event structures, I can imagine an 'event structure semantics' for Petri nets where your Petri net has tokens in its places and an 'event' occurs each time there's a 'transition' and the tokens move. Two such events occur here:
but events naturally form a poset, where means that one can occur after another.
This would be what computer scientists call a nondeterministic semantics: in each state of the system it's possible for certain events to occur, moving it to another state, and that's all we know.
David Corfield (Apr 19 2025 at 07:28):John Baez said:
I can imagine an 'event structure semantics' for Petri nets where your Petri net has tokens in its places and an 'event' occurs each time there's a 'transition' and the tokens move.
That sounds right. Events to represent the transition firings of nets.
We need the likes of @Sam Staton to help us. He worked with Winskel himself
Or @Hugo Paquet who currently works with them, as with
David Corfield (Apr 19 2025 at 07:43):By the way, we weren't looking at event structures for fancy things like concurrent programming, rather to specify some medical procedure.
David Karcher's 'higher-order dynamic-causality event structure' (hdes) are used for a clinical case study in Chap. 5 of his thesis, Event Structures with Higher-Order Dynamics:
A couple of paragraphs on why one might prefer event structures to Petri nets:
Damiano Mazza (Apr 19 2025 at 07:54):I know event structures relatively well, at least in their incarnation as "prime event structures" (as David mentioned, there are tons of variants). Petri nets abstract computational processes as certain kinds of machines based on tokens and transitions. Prime event structures are more algebraic: they abstract a computational process in term of events that may or may not happen, with a causal order saying which events are necessary for a given event to be enabled, and a conflict relation saying which events cannot both happen in a consistent evolution of the system.
For example, if you have three events with and in conflict with , then you are saying that, when you run your computational process, one of or may happen (not , because it needs ), and if happens, then that's it, nothing else may happen, otherwise, if happens, then is allowed to happen (but not ).
A key notion for event structures is that of a configuration, which is a conflict-free downward-closed set of events. It is a sort of a possible "snapshot" of the system at some point during its evolution. In the above example, we have four configurations: , , , .
Intuitively, Petri nets may be assigned an event structure in the way John sketched. Conversely, one may look for a Petri net "implementing" a certain event structure. This is where one needs to be precise about what kind of Petri nets and what kind of event structures one is considering. For example, I'm pretty sure that general Petri nets are "more expressive" than prime event structures, in the sense that there are some Petri nets that you may not faithfully interpret as a prime event structure (but you may interpret them using the more general version of event structures). This is because prime event structures refuse "disjunctive causation", that is, the fact that an event may be caused by or .
Unlike Petri nets, event structures were studied from the categorical viewpoint right from the start. One may define a category whose objects are (prime) event structures, and the properties/structure of this category (products, coproducts, symmetric monoidal structure, etc.) correspond to ways of building bigger computational systems from smaller ones, so that one may interpret concurrent programming languages compositionally. In other words, syntactic constructs correspond to categorical operations on event structures, which is something that programming language theorists like very much in general.
One of the fundamental motivations for assigning an event structure to a concurrent program is to study program equivalence. For that, several notions of equivalence of event structures have been introduced, all variants of something called bisimilarity. If and are two programs and , their event structures, the fact that and are bisimilar tells us that and behave in the same way, according to a suitable notion of "sameness". Bisimilarity (or, rather, the key underlying notion, called bisimulation) have been studied from a categorical perspective using the notion of "open map".
More recently, Winskel and collaborators used event structures as the starting point of a very general kind of games semantics for programming languages, called concurrent games. But that's another story.
Back to the main question, I don't know how event structures are viewed in the ACT community, apparently they are not very well known at all! But there's already a bunch of categorical machinery available for them, which makes them rather immediately accessible to the community. They are certainly very versatile, because they may describe arbitrary processes, not necessarily coming from the execution of a program. However, one has to see if and how all the machinery (typically, bisimulations) are still meaningful outside of the context of programming languages.
Hugo Paquet (Apr 19 2025 at 09:42):A Petri net can be "unfolded" to a particular kind of loop-free Petri net called an occurrence net. This unfolding should be a right adjoint to the inclusion of occurrence nets into Petri nets. Then there is another adjunction between the category of occurrence nets and the category of event structures, described in this 1987 paper, where events correspond precisely to transitions. By composing these adjunctions we get an adjunction between Petri nets and event structures.
But it's a bit hard to make all this precise because of some symmetry issues. So either we can add symmetry to event structures and occurrence nets (like in this paper), or we can give each token a precise identity (like in this paper). (Or we can restrict the Petri nets to safe Petri nets, but that's a strong restriction.)
Sam Staton (Apr 19 2025 at 10:20):Hi! Just to add an analogy that might or might not be self-evident here: the difference between an automaton, and the language it accepts.
Sam Staton (Apr 19 2025 at 10:20):Event structures are intended as a semantic domain (analogous to regular languages). Petri nets can be ad-hoc / intensional / have unobservable differences e.g. where the loops are (analogous to automata). Of course, automata are still useful! and so are Petri nets.
Sam Staton (Apr 19 2025 at 10:20):I would really like to understand how this fits with the bio and chemistry applications. Is it that you don't yet care about an extensional semantic domain, or is it that loops _are_ observable, or is it that you actually have occurrence nets?
John Baez (Apr 19 2025 at 18:08):What do you mean by "loops"? I can imagine a possible example: a transition from a single place to itself. When this transition fires, the marking of the Petri net does not change.
In chemistry this would count as "nothing happening" - we don't care about the personal experiences of individual molecules. So in chemistry nobody would even dream of using a Petri net with a transition from a place to itself.
In biology the use of Petri nets is not so deeply developed, but people mainly care about the changes in populations, so again they'd probably consider this firing a nonevent.
Sam Staton (Apr 20 2025 at 07:41):Thanks @John Baez, yes I meant that or the sort of thing in this wikipedia picture, or anything else that would be unfolded into a more canonical shape when converting to event structures. Is this detailed structure important in the applications or can it be unfolded away?
John Baez (Apr 20 2025 at 18:50):I don't understand "unfolding" and I don't see what is weird about the Petri net you just showed me (unlike a Petri net that has a transition going from a place to itself, which would be considered "chemically irrelevant"). I guess I'm missing something.
Hugo Paquet (Apr 20 2025 at 20:29):Unfolding is about getting an acyclic Petri net out of a Petri net like the one in the picture. That's why an event structure is defined as a partial order (not just a preorder), and there's an induced Scott domain.
It's interesting that the cycle would be chemically irrelevant, because the semantics would be an infinite chain of events. Probably I don't have the right intuition.
John Baez (Apr 20 2025 at 21:14):The idea is that transitions that don't change the marking at all are chemically irrelevant. They don't change how many molecules you have of each kind.
Chemists mainly care about the rate equation and master equation semantics, which give differential equations from Petri nets where each transition is equipped with a positive real number. Transitions that don't change the marking can be removed without changing these differential equations.
John Baez (Apr 20 2025 at 21:15):On the other hand, every transition in the Petri net you just showed us changes the marking when it fires.
Sam Staton (Apr 21 2025 at 08:31):Thanks John. I don't know whether you're still unclear about unfoldings, here is a picture (taken from Hayman and Winskel):
image.png
image.png
The first Petri net has cycles, and the second is its unfolding, which happens to be infinite. Do you see what I mean from this illustration?
(Edit: apologies, that picture of unfolding is maybe the kind you are saying isn't chemically relevant. Maybe this one is clearer (taken from Glynn Winskel's lecture notes):)
image.png
image.png
Sam Staton (Apr 21 2025 at 08:32):Many nets will unfold to the same thing. In CS applications, a net typically has the same semantics as its unfolding. Is that true in other domains?
Sam Staton (Apr 21 2025 at 08:32):Nets with cycles will be useful for specification and verification, since they are more often finite. But the unfolded structure (~event structure) is typically regarded as the canonical meaning. Perhaps you have no need for this because you immediately go to another mathematical domain for meaning?
John Baez (Apr 21 2025 at 16:49):Thanks, I think I get unfoldings now, from your pictures.
In chemistry we indeed usually treat Petri nets as merely a syntax for writing differential equations: either an ordinary differential equation (rate equation) or stochastic differential equation (master equation).
In chemistry, Petri nets very often have cycles, and that's not considered a bad thing, since it merely says that some collection of chemicals can be destroyed in some reactions and later created by others. Unfolding would amount to creating imaginary new chemicals to avoid this, which we don't want - though it might be good for some technical reason I've never seen yet!
The only cycles that are shunned consist of a single transition whose multiset of input places is exactly equal to its multiset of output places, because firing this transition will not affect the marking. And they're shunned out of convenience rather than necessity: you can remove them since doing so doesn't affect the semantics, but you can equally well leave them in. So the theory allows them, but practitioners never use them.
Nathan Corbyn (Apr 22 2025 at 07:43):When unfolding, it is normal to record the state in the petri net where a node comes from. That is, one can still label the unfolding with the names of the chemicals, it just may be the case the same chemical occurs multiple times. (These are the ‘imaginary’ chemicals.) The result is that the unfolding is additionally recording something akin to the history of the reactants, rather than just what molecules we have at a given time.
David Corfield (Apr 22 2025 at 08:24):John Baez said:
Unfolding would amount to creating imaginary new chemicals to avoid this, which we don't want - though it might be good for some technical reason I've never seen yet!
To generalise what I see as @Nathan Corbyn's correct response, just because it's possible to unfold a Petri net to an occurrence net, and we may see the latter as a special kind of the former, doesn't mean that when using occurrence nets we're only dealing with a special version of the kind of thing we're looking to capture with Petri nets.
Could we liken the difference to that in physics between a phase space and a trajectory space?
Is it just for historical reasons that we're seeing different domains of use for these constructions? I mentioned above Karcher using an event structure to depict a medical case study. Is there anything to stop some kind of event structure formalism depicting , say, chemical reactions with rates?
David Corfield (Apr 22 2025 at 09:04):Interesting from Joachim Kock in Whole-grain Petri nets and processes:
Reminiscent of universal covering spaces. Hmm, is there any interesting [[covering space theory]] for Petri nets?
David Corfield (Apr 23 2025 at 10:14):If whole-grain Petri nets are the image of pre-nets inside (Categories of Nets, p. 3) and whole-grain Petri nets can be unfolded to a universal unfolding, is the same true of -nets?
But Kock attributes the capacity to find a universal unfolding for all Petri nets to the whole-grain setting,
the symmetry problems simply disappear: Winskel’s ideas, notions and proof arguments in the safe case now work in full generality.
-nets seem to be combining individual and collective token styles, so does the symmetry problem for universal unfolding return here?
And then what, if any, is the relation between Winskel-style unfolding and the execution semantics of the monoidal category of a net's “executions”?
Hugo Paquet (Apr 23 2025 at 10:28):I'm not sure about -nets, but for your last question, one difference is that the unfolding only looks at executions from a fixed initial marking, whereas the monoidal category consists of all executions between arbitrary markings.
David Corfield (Apr 23 2025 at 10:58):Thanks. So perhaps the latter is the more natural construction, like the fundamental groupoid over the fundamental group, etc.