Open Petri Nets (Part 3)

I’ve been talking about my new paper with Jade Master:

• John Baez and Jade Master, Open Petri nets, Mathematical Structures in Computer Science, 30 (2020), 314–341.

In Part 1 we saw the double category of open Petri nets; in Part 2 we saw the reachability semantics for open Petri nets as a double functor. Now I’d like to wrap up by showing you the engine beneath the hood of our results.

I fell in love with Petri nets when I realized that they were really just presentations of free symmetric monoidal categories. If you like category theory, this turns Petri nets from something mysterious into something attractive.

In any category you can compose morphisms f\colon X \to Y and g\colon Y \to Z and get a morphism gf \colon X \to Z. In a monoidal category you can also tensor morphisms f \colon X \to X' and g \colon Y \to Y' and get a morphism f \otimes g \colon X \otimes X' \to Y \otimes Y'. This of course relies on your ability to tensor objects. In a symmetric monoidal category you also have X \otimes Y \cong Y \otimes X. And of course, there is more to it than this. But this is enough to get started.

A Petri net has ‘places’ and also ‘transitions’ going between multisets of places:

From this data we can try to generate a symmetric monoidal category whose objects are built from the places and whose morphisms are built from the transitions. So, for example, the above Petri net would give a symmetric monoidal category with an object

2 susceptible + infected

and a morphism from this to the object

susceptible + 2 infected

(built using the transition infection), and a morphism
from this to the object

susceptible + infected + resistant

(built using the transition recovery) and so on. Here we are using + to denote the tensor product in our symmetric monoidal category, as usual in chemistry.

When we do this sort of construction, the resulting symmetric monoidal category is ‘free’. That is, we are not imposing any really interesting equations: the objects are freely generated by the places in our Petri net by tensoring, and the morphisms are freely generated by the transitions by tensoring and composition.

That’s the basic idea. The problem is making this idea precise!

Many people have tried in many different ways. I like this approach the best:

• José Meseguer and Ugo Montanari, Petri nets are monoids, Information and Computation 88 (1990), 105–155.

but I think it can be simplified a bit, so let me describe what Jade and I did in our paper.

The problem is that there are different notions of symmetric monoidal category, and also different notions of morphism between Petri nets. We take the maximally strict approach, and work with ‘commutative’ monoidal categories. These are just commutative monoid objects in \mathrm{Cat}, so their associator:

\alpha_{A,B,C} \colon (A + B) + C \stackrel{\sim}{\longrightarrow} A + (B + C)

their left and right unitor:

\lambda_A \colon 0 + A \stackrel{\sim}{\longrightarrow} A

\rho_A \colon A + 0 \stackrel{\sim}{\longrightarrow} A

and even—disturbingly—their braiding:

\sigma_{A,B} \colon A + B \stackrel{\sim}{\longrightarrow} B + A

are all identity morphisms.

The last would ordinarily be seen as ‘going too far’, since while every symmetric monoidal category is equivalent to one with trivial associator and unitors, this ceases to be true if we also require the braiding to be trivial. However, it seems that Petri nets most naturally serve to present symmetric monoidal categories of this very strict sort. There just isn’t enough information in a Petri net to make it worthwhile giving them a nontrivial braiding

\sigma_{A,B} \colon A + B \stackrel{\sim}{\longrightarrow} B+A

It took me a while to accept this, but now it seem obvious. If you want a nontrivial braiding, you should be using something a bit fancier than a Petri net.

Thus, we construct adjoint functors between a category of Petri nets, which we call \textrm{Petri}, and a category of ‘commutative monoidal categories’, which we call \textrm{CMC}.

An object of \textrm{Petri} is a Petri net: that is, a set S of places, a set T of transitions, and source and target functions

s, t \colon T \to \mathbb{N}[S]

where \mathbb{N}[S] is the underlying set of the free commutative monoid on S.

More concretely, \mathbb{N}[S] is the set of formal finite linear combinations of elements of S with natural number coefficients. The set S naturally includes in \mathbb{N}[S], and for any function

f \colon S \to S'

there is a unique monoid homomorphism

\mathbb{N}[f] \colon \mathbb{N}[S] \to \mathbb{N}[S']

extending f.

A Petri net morphism from a Petri net

s, t \colon T \to \mathbb{N}[S]

to a Petri net

s', t' \colon T' \to \mathbb{N}[S']

is a pair of functions

f \colon T \to T'

g \colon S \to S'

making the two obvious diagrams commute:

There is a category \textrm{Petri} with Petri nets as objects and Petri net morphisms as morphisms.

On the other hand, a commutative monoidal category is a commutative monoid object in \mathrm{Cat}. Explicitly, it’s a strict monoidal category (C,+,0) such that for all objects A and B we have

A + B = B + A

and for all morphisms f and g

f + g = g + f

Note that a commutative monoidal category is the same as a strict symmetric monoidal category where the symmetry isomorphisms

\sigma_{A,B} \colon A + B \stackrel{\sim}{\longrightarrow} B+A

are all identity morphisms. Every strict monoidal functor between commutative monoidal categories is automatically a strict symmetric monoidal functor. So, we let \mathrm{CMC} be the category whose objects are commutative monoidal categories and whose morphisms are strict monoidal functors.

There’s a functor

U \colon \mathrm{CMC} \to \mathrm{Petri}

sending any commutative monoidal category C to its underlying Petri net. This Petri net has the set of objects \mathrm{Ob}(C) as its set of places and the set of morphisms \mathrm{Mor}(C) as its set of transitions, and

s, t \colon \mathrm{Mor}(C) \to \mathrm{Ob}(C) \hookrightarrow \mathbb{N}[\mathrm{Ob}(C)]

as its source and target maps.

Proposition. The functor U \colon \mathrm{CMC} \to \mathrm{Petri} has a left adjoint

F \colon \mathrm{Petri} \to \mathrm{CMC}

This is Proposition 10 in our paper, and we give an explicit construction of this left adjoint.

So that’s our conception of the free commutative monoidal category on a Petri net. It’s pretty simple. How could anyone have done anything else?

Montanari and Meseguer do almost the same thing, but our category of Petri nets is a subcategory of theirs: our morphisms of Petri nets send places to places, while they allow more general maps that send a place to a formal linear combination of places. On the other hand, they consider a full subcategory of our \mathrm{CMC} containing only commutative monoidal categories whose objects form a free commutative monoid.

Other papers do a variety of more complicated things. I don’t have the energy to explain them all, but you can see some here:

• Pierpaolo Degano, José Meseguer and Ugo Montanari, Axiomatizing net computations and processes, in Logic in Computer Science 1989, IEEE, New Jersey, 1989, pp. 175–185.

• Vladimiro Sassone, Strong concatenable processes: an approach to the category of Petri net computations, BRICS Report Series, Dept. of Computer Science, U. Aarhus, 1994.

• Vladimiro Sassone, On the category of Petri net computations, in Colloquium on Trees in Algebra and Programming, Springer, Berlin, 1995.

• Vladimiro Sassone, An axiomatization of the algebra of Petri net concatenable processes, in Theoretical Computer Science 170 (1996), 277–296.

• Vladimiro Sassone and Pavel Sobociński, A congruence for Petri nets, Electronic Notes in Theoretical Computer Science 127 (2005), 107–120.

Getting the free commutative monoidal category on a Petri net right is key to developing the reachability semantics for open Petri nets in a nice way. But to see that, you’ll have to read our paper!

• Part 1: the double category of open Petri nets.

• Part 2: the reachability semantics for open Petri nets.

• Part 3: the free symmetric monoidal category on a Petri net.

This entry was posted on Sunday, August 19th, 2018 at 8:31 am and is filed under computer science, mathematics, networks. 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.

14 Responses to Open Petri Nets (Part 3)

  1. Phillip Helbig says:
    20 August, 2018 at 7:36 am

    Jade Master: Sounds like a superhero, or some science-fiction character. The full name Jade Edenstar Master is even cooler.

    Which scientists have the best names? The astronomer Alan Heavens is certainly high up on the list.

    Reply
    • John Baez says:
      20 August, 2018 at 11:47 am

      “Jade Master” sounds like someone out of a Chinese martial arts movie. Jade is indeed a cool guy, but I’ve never seen him break a brick with his bare hands.

      I think the best scientists make their own names sound cool… just by being cool. Names like “Pythagoras”, “Einstein” and “Gödel” have become iconic.

      Reply
      • Phillip Helbig says:
        21 August, 2018 at 6:45 pm

        Gödel and Einstein are rare names. So are Beethoven and Mozart. Bach is relatively common, and Schubert even more so. Tegmark is very, very rare. Newton is relatively common, Darwin relatively rare. There might be only one Lavoisier.

        So, there are famous musicians and scientists with both common and uncommon last names. (Of course, there is a musician and a scientist with the same relatively uncommon last name. :-) ) Nevertheless, among scientists or musicians, is the fraction with uncommon last names higher than in the general population? Among those with uncommon last names, are there more scientists and musicians than in the general population? Faraday, Schrödinger, Heisenberg, Born, Jordan, Planck, Feynman, Witten—all relatively uncommon.

        Reply
        • Mart Malakoff says:
          22 August, 2018 at 12:24 pm

          Or maybe having an uncommon last name may turn you into a scientist/math person, because you are already labeled as ‘non-normal’. I wonder if this holds for first names too, and what happens if both your first and last names are uncommmon—perhaps a double dis/ability. .

        • Phillip Helbig says:
          23 August, 2018 at 8:32 am

          Yes, I was thinking that maybe being uncommon in some way magically transforms one from a jock into a scientist. :-)

          The unusual name might help as well, since people will know that it is your work. Max Tegmark famously adopted his mother’s maiden name (which is rare, even in Sweden; there are just a handful of people with this name, all closely related to Max) when he arrived in California. He had previously been Max Shapiro (son of mathematician Harold Shapiro), which is a very rare name in Sweden, but not that uncommon in the USA. There is more than one Shapiro in astrophysics.

          Of course, “common” refers to the country/language in question. Bach is not as common as, say, Schmidt or Schneider, but is relatively common, maybe as common as Meyers (in various spellings) in the USA, say. I’ve never heard of anyone else named Beethoven or Mozart.

          Interestingly, Johann Sebastian Bach was not that famous in his own time. The most famous composer in Germany at the time, and friend of JSB, was Georg Philipp Telemann (Godfather of Carl Philipp Emanuel Bach), who also sports a really rare name.

          Most people would probably put Bach at the top of the list of Baroque composers (or, maybe, even of all composers), with Händel an Vivaldi close behind. These are to some extent the “big three”. Then, there are the rest: Telemann, Boyce, Scarlatti (more than one), Corelli, Soler, Schütz (Baroque, but a previous generation), Lully, Rameu, Albinoni, Couperin, Pachelbel, Graupner, etc. Personally, I would put Telemann between Bach and Vivaldi, probably closer to Bach.

          For some reason, Telemann is not that well known nor are his works performed that often, but he is worth checking out. He also wrote a huge amount of music, much of it lost—about 6000 works altogether. Mozart was also prolific, but died young; Telemann lived to be 86. Definitely worth checking out.

          Perhaps his huge output influenced his reputation, because many couldn’t believe that one could combine quality with quantity. Although he did write a large number of works, they are not just variations on a theme (like, say, Scarlatti’s harpsichord stuff), but very diverse, probably more diverse than that of other composers of the time.

          Bach achieved a bit of local fame when he became cantor in Leipzig. Interestingly, the first person on the short list was Telemann, who declined after negotiating a higher salary in Hamburg (where he spent most of his life, also dying there). After number 2 (Graupner) also declined, Bach got the job.

          Telemann knew both Bach and Händel, but the latter two didn’t know each other. Some say one had never heard the music of the other, so similarities are down mostly to common influences (particularly somewhat earlier Italian music; Händel had spent some time in Italy, and Bach was a fan of Vivaldi). They were otherwise quite different: Bach had two wives and 20 children; Händel was probably gay (though, of course, at the time, not openly so) and had no children; Bach worked mostly in what even today is still rather out of the way, Händel worked in the biggest city in the world and was a friend of the king; Bach wrote in every genre of the time except opera; at least early on, Händel was famous mainly for his operas; Bach struggled with debt; Händel was rich.

          Old joke: What did Mozart do after he died? He decomposed.

        • Mart Malakoff says:
          26 August, 2018 at 9:24 am

          I have a suburb of Paris, a town in Russia and one in Texas, and a gold mine in California (near where all those fires in Redding /Mt Shasta were) named after me–or at least have same name .

          Godel always i found a fascinating name because its similar to god, and ‘waiting for godot’ (famous play).

          I have a degree in chemistry and from wikipedia i see that Petri nets were invented to formalize chemical reactions though they were not discussed in my classes . (i actually did very little lab chemistry –i basically studied quantum and physcial chemistry (statistical mechanics) at a low level–i was into theoretical biology (Turing patterns—reaction-diffusion equations, ecological networks) but they didnt have a degree program in that so i called it chemistry–it could be alchemy.

          I first came across Petri nets i think in a book by Judea Pearl on ‘causality’ (in my area we may call this ‘casualties’ due to all the local violence –i went to a community gathering called ‘peace out, don’t smoke the brothers’ yesterday on this issue .)

          I’m trying to decide if category theory and all these other formalisms (bond graphs, etc) can be useful for my own ‘projects’—-these are actually social and economic issues– . how do you combine people and tasks into teams or working groups which are functional (not disfunctional). In economics I think this is called a ‘matching problem’, and there are similar problems for things like marriages and where to go to college and what to study.

          In statistical physics and stochastic processes i think trying to calculate ‘reachability’ is called calculating a ‘stopping time’.

          I think I can see the usefulness of this formalism but its at the ‘rocket science’ level while more people i know including me arent at a level much above figuring out how to tie their shoes.

          Since i have done alot of hiking (spent more time on that than math though i always carry some math papers with me) i am always trying to calculate probabilities for the ‘shortest path’ to the ‘highest mountain’ or nice place (usually a ravine where you find the interesting flora and fauna) . Sometimes you end up in a box canyon, other times you find a fairly easy route.

      • John Baez says:
        22 August, 2018 at 4:53 am

        I’ve wondered about this too. Could it be that having an unusual name helps you get remembered which helps you become famous? One would need to do some studies.

        I hadn’t known Bach was a relatively common name. It may be in Germany, but not in the United States… so when I hear the name “Bach” I instantly think of the Bach, the master of counterpoint… C. P. E. Bach.

        Reply
  2. Noam Zeilberger says:
    20 August, 2018 at 6:12 pm

    [It looks like there is a typo in the first example: I think you mean that there is a morphism [2 susceptible + infected] \to [susceptible + 2 infected] built using the transition [infection].]

    I see that in the paper you talk about the classical reachability problem for Petri nets (deciding whether one marking n is reachable from another marking m via a sequence of transitions in the net P), and observe that this is equivalent to the existence of a morphism m \to n in the free commutative monoidal category FP. I’m not an expert on that problem, but do you think this observation could provide any new insights? For example, is there any hope of proving some kind of coherence theorem for the categories FP that would give a new decision procedure for reachability?

    Reply
    • John Baez says:
      21 August, 2018 at 2:26 am

      I have no idea. The reachability problem is famously subtle, and Section 25.1 of my book Quantum Techniques for Stochastic Mechanics describes the comic history of errors that have been made in trying to study it. So, it’s the last thing in the world I would try to work on, even though it’s fascinating.

      Reply
      • Noam Zeilberger says:
        21 August, 2018 at 9:33 am

        Fair enough! Thanks for the pointer to the interesting historical discussion.

        Reply
      • John Baez says:
        21 August, 2018 at 10:57 am

        Upon thinking a bit more I’ll venture this: you should be able to use open Petri nets to deliberately design Petri nets for which the reachability problem is easier to solve than for general Petri nets. Our comments on ‘one-way Petri nets’ in the Conclusion point at the sort of thing I mean. My feeling is that certain types of ‘looping’ behavior make the reachability problem hard to solve, and you could deliberately avoid this if you wanted. This would reduce the computational power of Petri nets, but very often when you’re trying to design a simple reliable system you’re willing to sacrifice computational power.

        A while ago I stumbled across a workshop at the Santa Fe Institute on Turing-incomplete machines for enhanced computer security. (I can’t find it online anymore!) Petri nets are already Turing-incomplete (unless one add extra bells and whistles), but since their computational complexity is somewhere between EXPSPACE and something much worse (and nobody knows where—read the comic history of errors), it may pay to dumb them down a bit further for some purposes.

        Reply
    • John Baez says:
      22 August, 2018 at 5:01 am

      Noam wrote:

      It looks like there is a typo in the first example: I think you mean that there is a morphism [2 susceptible + infected] \to [susceptible + 2 infected] built using the transition [infection].

      You’re right. Thanks! Fixed.

      Reply
  3. Complex Adaptive System Design (Part 8) | Azimuth says:
    22 August, 2018 at 10:36 am

    I would like to dive deeper into the details, but this is probably enough for one post. We’re writing a couple of papers, so I’ll have more to say later! I will say, though, that we use some math I’ve just developed with my grad student Jade Master, explained here:

    • Open Petri nets (part 3), Azimuth, 19 August 2018.

    Reply
  4. Structured Cospans and Petri Nets | Azimuth says:
    6 April, 2020 at 6:34 pm

    This talk on structured cospans and Petri nets is the second of a two-part series, but it should be understandable on its own. The first part is on structured cospans and double categories.

    You can see my talk live on YouTube here, with simultaneous discussion on the Category Theory Community Server. (To join this, click here.) The talk will be recorded and remain available on YouTube.

    You can already see the slides here.

    Structured cospans and Petri nets

    Abstract. “Structured cospans” are a general way to study networks with inputs and outputs. Here we illustrate this using a type of network popular in theoretical computer science: Petri nets. An “open” Petri net is one with certain places designated as inputs and outputs. We can compose open Petri nets by gluing the outputs of one to the inputs of another. Using the formalism of structured cospans, open Petri nets can be treated as morphisms of a symmetric monoidal category—or better, a symmetric monoidal double category. We explain two forms of semantics for open Petri nets using symmetric monoidal double functors out of this double category. The first, an operational semantics, gives for each open Petri net a category whose morphisms are the processes that this net can carry out. The second, a “reachability” semantics, simply says what these processes can accomplish. This is joint work with Kenny Courser and Jade Master.

    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.