https://johncarlosbaez.wordpress.com/2021/01/17/categories-of-nets/ Azimuth * Home * About Categories of Nets I've been thinking about Petri nets a lot. Around 2010, I got excited about using them to describe chemical reactions, population dynamics and more, using ideas taken from quantum physics. Then I started working with my student Blake Pollard on 'open' Petri nets, which you can glue together to form larger Petri nets. Blake and I focused on their applications to chemistry, but later my student Jade Master and I applied them to computer science and brought in some new math. I was delighted when Evan Patterson and Micah Halter used all this math, along with ideas of Joachim Kock, to develop software for rapidly assembling models of COVID-19. Now I'm happy to announce that Jade and I have teamed up with Fabrizio Genovese and Mike Shulman to straighten out a lot of mysteries concerning Petri nets and their variants: * John Baez, Fabrizio Genovese, Jade Master and Mike Shulman, Categories of nets. This paper is full of interesting ideas, but I'll just tell you the basic framework. A Petri net is a seemingly simple thing: [petri_net] It consists of places (drawn as circles) and transitions (drawn as boxes), with directed edges called arcs from places to transitions and from transitions to places. The idea is that when you use a Petri net, you put dots called tokens in the places, and then move them around using the transitions: [petri_net_with_tokens] A Petri net is actually a way of describing a monoidal category. A way of putting a bunch of tokens in the places gives an object of this category, and a way of moving them around repeatedly (as above) gives a morphism. The idea sounds straightforward enough. But it conceals some subtleties, which researchers have been struggling with for at least 30 years. There are various ways to make the definition of Petri net precise. For example: is there a finite set of arcs from a given place to a given transition (and the other way around), or merely a natural number of arcs? If there is a finite set, is this set equipped with an ordering or not? Furthermore, what is a morphism between Petri nets? Different answers are good for different purposes. In the so-called 'individual token philosophy', we allow a finite set of tokens in each place. In the 'collective token philosophy', we merely allow a natural number of tokens in each place. It's like the difference between having 4 individual workers named John, Fabrizio, Jade and Mike where you can tell who did what, and having 4 anonymous workers: nameless drones. Our goal was to sort this out all and make it crystal clear. We focus on 3 kinds of net, each of which naturally generates its own kind of monoidal category: * pre-nets, which generate free strict monoidal categories. * S-nets, which generate free symmetric strict monoidal categories. * Petri nets, which generate free commutative monoidal categories. These three kinds of monoidal category differ in how 'commutative' they are: * In a strict monoidal category we typically have x \otimes y \ne y \ otimes x. * In a strict symmetric monoidal category we have for each pair of objects a chosen isomorphism x \otimes y \cong y \otimes x. * A commutative monoidal category is a symmetric strict monoidal category where the symmetry isomorphisms are all identities, so x \ otimes y = y \otimes x. So, we have a spectrum running from hardcore individualism, where two different things of the same type are never interchangeable... to hardcore collectivism, where two different things of the same type are so interchangeable that switching them counts as doing nothing at all! In the theory of Petri nets and their variants, the two extremes have been studied better than the middle. You can summarize the story with this diagram: [categories_of_nets] There are three different categories of nets at bottom, and three diffferent categories of monoidal categories on top -- all related by adjoint functors! Here the left adjoints point up the page -- since different kinds of nets freely generate different kinds of monoidal categories -- and also to the right, in the direction of increasing 'commutativity'. If you're a category theorist you'll recognize at least two of the three categories on top: * \mathsf{StrMC}, with strict monoidal categories as objects and strict monoidal functors as morphisms. * \mathsf{SSMC}, with symmetric strict monoidal categories as objects and strict symmetric monoidal functors as their morphisms. * \mathsf{CMC}, with commutative monoidal categories as objects and strict symmetric monoidal functors as morphisms. A commutative monoidal category is a symmetric strict monoidal category where the symmetry is the identity. The categories of nets are probably less familiar. But they are simple enough. Here I'll just describe their objects. The morphisms are fairly obvious, but read our paper for details. * \mathsf{PreNet}, with pre-nets as objects. A pre-net consists of a set S of places, a set T of transitions, and a function T \to S^\ast\ times S^\ast, where S^\ast is the set of lists of elements of S. * \Sigma\mathsf{-net}, with S-nets as objects. A S-net consists of a set S, a groupoid T, and a discrete opfibration T \to P S \times P S^ {\mathrm{op}}, where P S is the free symmetric strict monoidal category generated by a set of objects S and no generating morphisms. * \mathsf{Petri}, with Petri nets as objects. A Petri net, as we use the term, consists of a set S, a set T, and a function T \to \mathbb {N}[S] \times \mathbb{N}[S], where \mathbb{N}[S] is the set of multisets of elements of S. What does this mean in practice? * In a pre-net, each transition has an ordered list of places as 'inputs' and an ordered list of places as 'outputs'. We cannot permute the inputs or outputs of a transition. * In a S-net, each transition has an ordered list of places as inputs and an ordered list of places as outputs. However, permuting the entries of these lists gives a new transition with a new list of inputs and a new list of outputs! * In a Petri net, each transition has a multiset of places as inputs and a multiset of places as outputs. A multiset is like an 'unordered list': entries can appear repeatedly, but the order makes no difference at all. So, pre-nets are rigidly individualist. Petri nets are rigidly collectivist. And S-nets are flexible, including both extremes as special cases! On the one hand, we can use the left adjoint functor \mathsf{PreNet} \to \Sigma\mathsf{-net} to freely generate S-nets from pre-nets. If we do this, we get S-nets such that permutations of inputs and outputs act freely on transitions. Joachim Kock has recently studied S-nets of this sort. He calls them whole-grain Petri nets, and he treats them as forming a category in their own right, but it's also the full image of the above functor. On the other hand, we can use the right adjoint functor \mathsf{Petri} \to \Sigma\mathsf{-net} to turn Petri nets into S-nets. If we do this, we get S-nets such that permutations of inputs and outputs act trivially on transitions: the permutations have no effect at all. I'm not going to explain how we got any of the adjunctions in this diagram: [categories_of_nets] That's where the interesting category theory comes in. Nor will I tell you about the various alternative mathematical viewpoints on S-nets... nor how we draw them. I also won't explain our work on open nets and open categories of all the various kinds. I'm hoping Mike Shulman will say some more about what we've done. That's why this blog article is optimistically titled "Part 1". But I hope you see the main point. There are three different kinds of things like Petri nets, each of which serves to freely generate a different kind of monoidal category. They're all interesting, and a lot of confusion can be avoided if we don't mix them up! Related This entry was posted on Sunday, January 17th, 2021 at 11:57 pm and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. Post navigation << Previous Post You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it. Cancel reply Enter your comment here... [ ] Fill in your details below or click an icon to log in: * * * * * Gravatar Email (required) (Address never made public) [ ] Name (required) [ ] Website [ ] WordPress.com Logo You are commenting using your WordPress.com account. ( Log Out / Change ) Google photo You are commenting using your Google account. ( Log Out / Change ) Twitter picture You are commenting using your Twitter account. ( Log Out / Change ) Facebook photo You are commenting using your Facebook account. ( Log Out / Change ) Cancel Connecting to %s [ ] Notify me of new comments via email. [ ] Notify me of new posts via email. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] This site uses Akismet to reduce spam. Learn how your comment data is processed. * latest posts: + Categories of Nets + This Week's Finds (1-50) + CP Violation + Applied Category Theory 2021 -- Adjoint School + Cosmic Censorship + Solar Neutrinos + Neutrino Puzzles (Part 2) + Neutrino Puzzles (Part 1) + Theoretical Physics in the 21st Century + Consolidated Appropriations Act, 2021 * latest comments: [ba9] Keith Harbaugh on Consolidated Appropriations Ac... [347] John Baez on This Week's Finds (... [b58] Brian Crabtree on This Week's Finds (... [ba9] Keith Harbaugh on Consolidated Appropriations Ac... [347] John Baez on Consolidated Appropriations Ac... [ba9] Keith Harbaugh on Consolidated Appropriations Ac... [347] John Baez on This Week's Finds (... [698] Phillip Helbig on This Week's Finds (... [347] John Baez on This Week's Finds (... [a4c] very old rando on This Week's Finds (... * How To Write Math Here: You can include math in your comments using LaTeX, but you need to do it this way: $latex E = mc^2$ You need the word 'latex' right after the first dollar sign, and it needs a space after it. Double dollar signs don't work, and other limitations apply, some described here. You can't preview comments here, but I'm happy to fix errors. * Read Posts On: + art (3) + astronomy (27) + azimuth (60) + biodiversity (37) + biology (103) + carbon emissions (72) + chemistry (70) + climate (152) + computer science (43) + conferences (75) + culture (4) + economics (29) + energy (46) + engineering (7) + game theory (29) + geography (3) + health (4) + history (2) + information and entropy (85) + jobs (11) + journals (4) + mathematics (452) + networks (178) + oceans (13) + physics (177) + probability (86) + psychology (6) + publishing (19) + puzzles (13) + quantum technologies (28) + questions (3) + risks (46) + seminars (20) + software (19) + strategies (34) + sustainability (64) + the practice of science (27) + this week's finds (18) * also visit these: + Azimuth Blog Overview + Azimuth Forum + Azimuth on Google+ + Azimuth Project + Bit Tooth Energy + Brave New Climate + Climate Change + Climate Disruption News + Climate Ethics + Do the Math + Dot Earth + Energy Bulletin + Environment 360 + Less Wrong + Planet3.0 + Question Everything + R-Squared Energy Blog + Real Climate Economics + RealClimate + Serendipity + The Science of Doom + Yale Environment 360 * RSS feeds: RSS Feed RSS - Posts RSS Feed RSS - Comments * Email Subscription: Enter your email address to subscribe to this blog and receive notifications of new posts by email. Join 5,074 other followers Email Address: [ ] Sign me up! * SEARCH: Search[ ] [Search] * Blog Stats: + 3,872,380 hits Blog at WordPress.com. [b]