Categories of Nets (Part 1)

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:

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:

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.

• Σ-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:

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 Σ-nets as objects. A Σ-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 Σ-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 Σ-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 Σ-nets from pre-nets. If we do this, we get Σ-nets such that permutations of inputs and outputs act freely on transitions. Joachim Kock has recently studied Σ-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 Σ-nets. If we do this, we get Σ-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:

That’s where the interesting category theory comes in. Nor will I tell you about the various alternative mathematical viewpoints on Σ-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!

• Part 1: three kinds of nets, and the kinds of monoidal categories they generate.

• Part 2: what kind of net is best for generating symmetric monoidal categories?

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.

2 Responses to Categories of Nets (Part 1)

  1. Christopher Upshaw says:
    18 January, 2021 at 9:46 pm

    If you forced the action of even permutations to be the identity would you get a sort of pre-fermionic system?

    Would describing the transition function of conservative cellular automata as a _-net be useful? I guess the _-monoidal category would be a sort of “macroscopic” view? I wonder what CS-comonad-like functor that goes from local to global transitions looks like in this context.

    Reply
  2. Science Advisor | Gödel's Lost Letter and P=NP says:
    21 January, 2021 at 10:45 pm

    Many of our peer bloggers step out to give general advice on science. Some conspicuously often take their advice and recommendations on natural sciences openly national. Others address it within smaller communities, but their ideas can be equally valuable. All may be worthy of consultation.

    Blogs

    The one rule we’re setting out now is that in order to be advising the advisor, the blogs must stay current. There are tons of terrific blogs that have stopped publishing altogether, or whose last new post is many moons ago. As for those who try to be reasonably current, Ken and I know how hard it is to do. So we took a three-week horizon—that is, who has posted something this year, 2021. That said, here are some of our favorite blogs on math and CS theory—after the first they are alphabetical by writer(s).

    What’s New Terence Tao
    The best math blog of all time. If you must read one, then this is the one. If you read two or more math blogs, then this is still the one. If you read two or more posts on this blog, then you qualify as a mathematician.

    Shtetl Optimized Scott Aaronson
    Wonderful blog. A brilliant combination of results, comments, and opinions. We have “encoded” his name in the previous section—see if you can spot where and how.

    Machine Learning Research Blog Francis Bach
    Focused on connections between optimization and learning. I conjecture that the key to solving some of our deep questions—PNP—could be resolved by machine-learning technology. I recall a year ago while talking with learning experts at Chicago that they said: We think SAT should have an algorithm that runs in time for some .

    Azimuth John Carlos Baez
    Often goes into physics and policy, such as today’s third post in a series on environmental policy and climate change. But two recent posts were on Petri nets and higher abstractions of them.

    Windows on Theory Boaz Barak
    This was originally a joint blog by researchers at the Microsoft Silicon Valley Research Center before it closed in 2014. Last week’s post is also on machine learning and theory.

    Mathematics under the Microscope Alexandre Borovik
    See his book with Tony Gardiner, The Essence of Mathematics. The spirit of the book is seen in this quote from George Pólya: It is better to solve one problem in five different ways than to solve five problems in one way.

    Turing’s Invisible Hand Felix Brandt, Michal Feldman, Jason Hartline, Bobby Kleinberg, Kevin Leyton-Brown, Noam Nisan, Vijay Vazirani
    They have an annotated version of John Nash’s 1955 letter to the NSA about the complexity of crypto, which beat Kurt Gödel’s “lost letter” by a whole year. As we joked on 4/1/12, if we had known about it, GLL would have been NLL.

    Peter Cameron’ Blog Peter Cameron
    This is where I found out about the appointment of Lander to Biden’s cabinet. Peter is at St. Andrews and emeritus from Queen Mary University of London. Ken wrote about him in his memorial for Peter Neumann.

    Quomodocumque Jordan Ellenberg
    He asks: Am I Supposed To Say Something About The Invasion Of The United States Capitol? He does. We haven’t. (We are mulling a post on quantitative matters from the pandemic and election that have become political footballs.)

    11011110 David Eppstein—the blog name is his initials DE in hexadecimal and his surname has a double-p.
    Right now he has a wonderful list of open questions and known results. For example there is a discussion of USA flag arrangements, and also the recent claimed solution of an almost 50 year old conjecture: A proof of the Erdős-Faber-Lóvasz conjecture by Dong Yeap Kang, Tom Kelly, Daniela Kuhn, Abhishek Methuku, Deryk Osthus.

    Explaining mathematics Joel Feinstein
    He asks: When proving there exists statements, is it enough to give just one example or do you have to prove it using the definitions, and so on? Read on for more.

    Computational Complexity Lance Fortnow and Bill Gasarch
    The CS theory blog that started it all. Continues to be one of the top blogs. Lance’s post on Tuesday says that “the way of most suggestions I make in my blog [is] a quick road to nowhere,” but the one in that post went somewhere.

    logic and more Joel Hamkins
    He discusses the math tea argument—one heard at an afternoon tea. I miss these very much, even though I do not drink tea. The argument is: There must be some real numbers that we cannot define, since there are uncountably many real numbers, but only countably many definitions. Is it correct? Read on about the talk he is giving tomorrow “in” Warsaw for an explanation.

    Combinatorics and more Gil Kalai
    Gil’s wonderful blog is a great place to see announcements of new results. He’s had a year-long series, “To cheer you up in difficult times”; its 18th installment links to a wonderful, thoughtful, entertaining, and provocative post by Igor Pak about conjectures. The 17th installment was about the Erdős-Faber-Lóvasz news.

    M-Phi Many authors
    All of the recent entries have been by Richard Pettigrew but they have a long list of previous contributors. The recent posts catch Ken’s eye because they employ the Brier score to reason philosophically about inaccuracy. Ken has employed his group’s novel adaptation of the Brier score in chess cheating cases all through the pandemic.

    Short, Fat Matrices Dustin Mixon
    He discusses a problem by Mario Krenn. The problem has consequences for quantum computation—and comes with cash prizes—one is €3,000.

    Turing Machine VZN
    Just nipped under with a New Year’s Day post on the Collatz conjecture. Ken used to know VZN’s full name but can’t find it now.

    Noncommutative Analysis Orr Shalit
    The issues here are important to quantum computation, since for operators and , is usually not true.

    in theory Luca Trevisan
    The only theory blog—I believe—that quotes Homer Simpson: “Marge, I agree with you—in theory. In theory, communism works. In theory.”

    Not Even Wrong Peter Woit
    Mathematical physics, for the most part, growing out from his 2005 book of that title critiquing string theory.

    We also link to sites such as John Awbrey’s Inquiry Into Inquiry and Pink Iguana that grow in beehive style, and sites with higher-volume politics and culture content such as prior probability by Enrique Guerra-Pujol.

    Open Problems

    We would be grateful for suggestions of additional mathematics and computing blogs that an advisor’s staff might consult.

    Reply

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.