Category Theory
Zulip Server
Archive

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.

Stream: event: MIT Categories Seminar

Topic: April 9 - John Baez's talk

John Baez (Apr 06 2020 at 01:10):

My talk is on "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.

You can see the slides for my talk here.

The talk is based on these papers:

• John Baez and Kenny Courser, Structured cospans.
• John Baez and Jade Master, Open Petri nets.
• Jade Master, Generalized Petri nets.

This talk is a followup to my earlier talk Structured cospans and double categories, but it should be understandable on its own.

Paolo Perrone (Apr 07 2020 at 17:53):

Hi all! We are trying out a double format. This week's talk will be both on Zoom and livestreamed on Youtube.

Paolo Perrone (Apr 07 2020 at 17:53):

Zoom Meeting:
https://zoom.us/j/988858130
Meeting ID: 988 858 130

Paolo Perrone (Apr 07 2020 at 17:53):

Youtube live stream:
https://youtu.be/41qNpHJXKV0

Paolo Perrone (Apr 07 2020 at 17:54):

See you in 2 days!

Paolo Perrone (Apr 09 2020 at 15:59):

Hello all! We start in a minute!

Tom Leinster (Apr 09 2020 at 16:05):

Has it started? Not seeing it on youtube

Paolo Perrone (Apr 09 2020 at 16:05):

It's started.
Anyone else having that problem?

Thomas Read (Apr 09 2020 at 16:05):

Youtube is working for me

Matteo Capucci (he/him) (Apr 09 2020 at 16:05):

I'm following fine on yt

Paolo Perrone (Apr 09 2020 at 16:05):

https://youtu.be/41qNpHJXKV0

Paolo Perrone (Apr 09 2020 at 16:06):

(Try to refresh and press play)

Tom Leinster (Apr 09 2020 at 16:06):

Yup, there now. Thanks for the URL, Paolo

Tom Leinster (Apr 09 2020 at 16:07):

I went to the youtube channel link (if that's what it is) linked to from http://brendanfong.com/seminar.html and couldn't see the live stream, despite refreshing/reloading the page

Paolo Perrone (Apr 09 2020 at 16:08):

I see. Maybe there's no link with the playlist yet. I'll look into that, thank you!

Brendan Fong (Apr 09 2020 at 16:08):

Thanks for pointing that out Tom -- yes, there is something wrong with the stream not appearing on the playlist

Tom Leinster (Apr 09 2020 at 16:08):

Sorry, it was the playlist link: https://www.youtube.com/playlist?list=PLhgq-BqyZ7i6Vh4nxlyhKDAMhlv1oWl5n

Brendan Fong (Apr 09 2020 at 16:09):

(If it helps, I've added the Zoom link to the website too: https://zoom.us/j/988858130)

Paolo Perrone (Apr 09 2020 at 16:10):

Thanks Brendan!

Paolo Perrone (Apr 09 2020 at 16:10):

(Should be listed in the playlist now.)

Tom Leinster (Apr 09 2020 at 16:12):

Thanks!

Sam Tenka (Apr 09 2020 at 16:43):

In Programming Languages, this distinction is sometimes called "small step" vs "big step" semantics :-)

Sam Tenka (Apr 09 2020 at 16:45):

but indistinguishable particles!

Sam Tenka (Apr 09 2020 at 16:55):

Question: since coeffs in N and indistinguishable particles, like bosons. Is there a fermionic analogue?

Brian Pinsky (Apr 09 2020 at 16:56):

Is there a nice generalization of Petri nets where the reachability problem is harder than the halting problem? I was wondering if giving the tokens individuality might do it

Matteo Capucci (he/him) (Apr 09 2020 at 16:57):

If you use free monoids on R (real numbers) instead of N, what do you get? Has it something to do with Petri nets with rates?

Sam Tenka (Apr 09 2020 at 16:58):

Question: what's an example application of Petri nets to understand something that otherwise would be cumbersome to analyze?

Joe Moeller (Apr 09 2020 at 16:59):

Whoever asked about rewriting, it might be worth look at Daniel Cicala's thesis: https://arxiv.org/pdf/1906.05443.pdf

Joe Moeller (Apr 09 2020 at 16:59):

He talks about rewriting with structured cospans

Gabriel Goren Roig (Apr 09 2020 at 16:59):

Basic question about the question John posed during the talk: doesn't tensoring of morphisms make the answer be more than 3?

Brian Pinsky (Apr 09 2020 at 17:00):

Is there a disjointness requirement on the inputs and outputs? It's harder to picture if they're not disjoint

Sam Tenka (Apr 09 2020 at 17:01):

Question (maybe better for offline): for Boltzmann Petri nets, would it be reasonable to consider petri net "coverings", where the base space is the bosonic version and the total space "marks" which particle is which by which copy they are in? (Imagining the total space as a bunch of disjoint copies, but it would be interesting to allow transitions)

Cole Comfort (Apr 09 2020 at 17:02):

Structured spans don't form a category in the case that the apex is labelled by the right adjoint. There is no identity

Joe Moeller (Apr 09 2020 at 17:02):

Or briefer than a thesis, Daniel also wrote a paper called Rewriting structured cospans: https://arxiv.org/abs/2001.09029

Sam Tenka (Apr 09 2020 at 17:03):

Matteo Capucci said:

If you use free monoids on R (real numbers) instead of N, what do you get? Has it something to do with Petri nets with rates?

I think the formalism would still have discrete time, but now continuous "amounts". So yes, a rate whose denominator is still discrete?

Sam Tenka (Apr 09 2020 at 17:05):

Brian Pinsky said:

Is there a nice generalization of Petri nets where the reachability problem is harder than the halting problem? I was wondering if giving the tokens individuality might do it

Any reachability question on a graph that can be described algorithmically should be no harder than the halting problem: Just ask whether {{the TM that searches breadth-first over all paths and halts when it finds a goal}} ever halts. One may strengthen "algorithmically" by adding an oracle; not sure how best to fit that concept in here.

Ralph Sarkis (Apr 09 2020 at 17:05):

Thanks @Joe Moeller

Eigil Rischel (Apr 09 2020 at 17:05):

Gabriel Goren said:

Basic question about the question John posed during the talk: doesn't tensoring of morphisms make the answer be more than 3?

We're looking for a map $X \otimes X \to Y \otimes Y$. The ingredients are maps $f,g: X \to Y$. The three maps are $(f \otimes 1_X) \circ (f \otimes 1_X), (f \otimes 1_X) \circ (g \otimes 1_X)$, and $(g \otimes 1_X) \circ (g \otimes 1_X)$. The commutativity of the category implies that the various other compositions, for instance $(g \otimes 1_X) \circ (f \otimes 1_X)$, are all equal to one of these.

Jade Master (Apr 09 2020 at 17:06):

Sam Tenka (naive student) said:

Matteo Capucci said:

If you use free monoids on R (real numbers) instead of N, what do you get? Has it something to do with Petri nets with rates?

I think the formalism would still have discrete time, but now continuous "amounts". So yes, a rate whose denominator is still discrete?

These fit within the framework of generalized Petri nets. They freely generate categories whose morphisms are ways of shuffling continuous resources around in given proportions.

Gabriel Goren Roig (Apr 09 2020 at 17:07):

Gabriel Goren said:

Basic question about the question John posed during the talk: doesn't tensoring of morphisms make the answer be more than 3?

Oh nevermind, the tensoring ends up being identical to the composite, and that's what John said at some point during the talk. Right?

Gabriel Goren Roig (Apr 09 2020 at 17:07):

I just saw your answer Eigil, thanks!

Jade Master (Apr 09 2020 at 17:13):

Thanks Eigil, the way that everything collapses in commutative monoidal categories like this is like a generalization of the Eckmann-Hilton argument.

Brian Pinsky (Apr 09 2020 at 17:15):

Is there a nice way to build petri nets with infinite sets of edges?

Jade Master (Apr 09 2020 at 17:16):

Sure. The set of transitions can be infinite. It's a bit harder to draw that way though.

Brian Pinsky (Apr 09 2020 at 17:17):

no I mean one transition requiring countably many inputs from one place

Jade Master (Apr 09 2020 at 17:18):

What would be the purpose of this?

Brian Pinsky (Apr 09 2020 at 17:19):

I was trying to think of ways to make Petri nets able to computer harder things, and one trick for doing that is giving it access to hard to compute sets of ordinals.

Joe Moeller (Apr 09 2020 at 17:19):

You can't have infinite edges between a given transition and a given species in the framework John is talking about.

Joe Moeller (Apr 09 2020 at 17:20):

You can have have infinite places, but you can't connect a transition to infinite places either. So a transition can never have access to infinite data in this framework.

Joe Moeller (Apr 09 2020 at 17:21):

But I could easily imagine there being a simple tweak to allow these though.

Sophie Libkind (Apr 09 2020 at 17:25):

Is there a relationship between the behavioral or operational semantics described and the gray boxing functor from open petri nets with rates to dynamical systems? Even though there's a discrete/continuous mismatch going on?

Jade Master (Apr 09 2020 at 17:28):

Sophie Libkind said:

Is there a relationship between the behavioral or operational semantics described and the gray boxing functor from open petri nets with rates to dynamical systems? Even though there's a discrete/continuous mismatch going on?

I don't know. But this is something that I would love to figure out!

Jade Master (Apr 09 2020 at 17:29):

The law of mass action in chemistry relates the discrete case to the rate equations you're describing.

Joe Moeller (Apr 09 2020 at 17:29):

I think it's worth pointing out that many ways of tweaking the definition of Petri net by changing what's playing the role of $\mathbb N$ are captured by a super general framework developed by @Jade Master in Generalized Petri nets https://arxiv.org/abs/1904.09091
The key ingredient is Lawvere theories.

Sophie Libkind (Apr 09 2020 at 17:32):

Jade Master said:

The law of mass action in chemistry relates the discrete case to the rate equations you're describing.

Neat! I haven't heard of the law of mass action before. Do you have a sound byte for it?

Paolo Perrone (Apr 09 2020 at 17:33):

Sophie Libkind said:

Jade Master said:

The law of mass action in chemistry relates the discrete case to the rate equations you're describing.

Neat! I haven't heard of the law of mass action before. Do you have a sound byte for it?

Roughly, the rate of a reaction is directly proportional to the concentration of each ingredient (multilinearly).

Sophie Libkind (Apr 09 2020 at 17:35):

thanks!

Sophie Libkind (Apr 09 2020 at 17:35):

That's sounds like how we define a diffeq from the petri net with rates

Jade Master (Apr 09 2020 at 17:36):

Right. What Paolo said is about all I know about the law of mass action.

Jade Master (Apr 09 2020 at 17:37):

Yeah. In John and Blake's paper they use the law of mass action to define the mapping from open Petri nets with rates to open dynamical systems.

John Baez (Apr 09 2020 at 17:41):

Hi! I just got some coffee...

John Baez (Apr 09 2020 at 17:42):

"That sounds like how we define a diffeq from the petri net with rates" - yes, that's what chemists call the law of mass action.

John Baez (Apr 09 2020 at 17:42):

They've also studied other laws, where we use a fancier function of the concentrations of each species to get the rate at which a reaction occurs (now I'm using chemistry jargon).

John Baez (Apr 09 2020 at 17:43):

Brian Pinsky said:

I was trying to think of ways to make Petri nets able to compute harder things, and one trick for doing that is giving it access to hard to compute sets of ordinals.

John Baez (Apr 09 2020 at 17:44):

You can replace $\mathbb{N}$ with any commutative "rig" - ring without negatives.

John Baez (Apr 09 2020 at 17:44):

There is a rig of all cardinals, with cardinal addition and multiplication.

John Baez (Apr 09 2020 at 17:44):

This is what I call a "big rig" - a rig that's too large to be a set.

John Baez (Apr 09 2020 at 17:45):

So if you wanted a monstrously big mutant version of a Petri net, you could use that.

John Baez (Apr 09 2020 at 17:46):

Brian Pinsky said:

Is there a nice generalization of Petri nets where the reachability problem is harder than the halting problem? I was wondering if giving the tokens individuality might do it.

John Baez (Apr 09 2020 at 17:46):

I really don't know if that does it. Interesting question.

John Baez (Apr 09 2020 at 17:47):

Matteo Capucci said:

If you use free monoids on R (real numbers) instead of N, what do you get? Has it something to do with Petri nets with rates?

John Baez (Apr 09 2020 at 17:47):

By the way, you meant "free $\mathbb{R}$-modules".

John Baez (Apr 09 2020 at 17:48):

The free $\mathbb{N}$-module on a set is the free commutative monoid on that set - this may have led to your monoid/module confusion.

John Baez (Apr 09 2020 at 17:49):

Gabriel Goren said:

Basic question about the question John posed during the talk: doesn't tensoring of morphisms make the answer be more than 3?

John Baez (Apr 09 2020 at 17:49):

No, it's just 3. If you write down more than 3 morphisms, I should be able to use some of the commutative monoidal category laws to show that some of them are equal.

Paolo Perrone (Apr 10 2020 at 02:48):

Hello. The video is up!
https://youtu.be/2CjTs9lmEHI
The HD version should be ready in a few minutes too (same link).

John Baez (Apr 10 2020 at 17:57):

Yay. Thanks for doing all this seminar organizing work, @Paolo Perrone.

Sophie Libkind (Apr 14 2020 at 03:38):

I have a small notation question. In your talk, $\mathbb{N}[S]$ refers to the free commutative monoid on the set of places $S$. In my head I think about an element of $\mathbb{N}[S]$ as an element of $\mathbb{N}^S$, i.e. a function $S \to \mathbb{N}$. Will this translation lead me astray? One guess is that if $S$ is infinite then $f: S \to \mathbb{N}$ only corresponds to an element of $\mathbb{N}[S]$ if $f(s)$ is non-zero for only finitely many $s$.

Faré (Apr 14 2020 at 04:48):

@Sophie Libkind Yes, it should be only functions with finite support, i.e. only a finite number of elements that aren't mapped to $0$.

John Baez (Apr 14 2020 at 05:22):

@Faré is correct. An element of the free commutative monoid on $S$ is a finite formal sum of elements of $S$, so we can identify it with a function $f: S \to \mathbb{N}$ that's zero except at finitely many points of $S$. The set of these functions is the same as the set of all functions $f : S \to \mathbb{N}$ iff $S$ is finite.

So, $\mathbb{N}[S]$ is naturally isomorphic to $\mathbb{N}^S$ as a commutative monoid when $S$ is finite, but not otherwise.

A subtler but extremely important point is that

$S \mapsto \mathbb{N}[S]$

defines a covariant functor $\mathsf{Set} \to \mathsf{CommMon}$, while

$S \mapsto \mathbb{N}^S$

defines a contravariant functor $\mathsf{Set} \to \mathsf{CommMon}$.

None of this depends on the special features of $\mathbb{N}$. A commutative monoid is an $\mathbb{N}$-module, but we can (and should) generalize everything I just said to modules of any commutative monoid $M$.

Here's how it goes. Let $M[S]$ be the free $M$-module on a set $S$, and $M^S$ be the $M$-module of functions from $S$ to $M$. In the case of finite sets we can use the isomorphism $\mathbb{M}[S] \cong \mathbb{M}^S$ to make

$S \mapsto \mathbb{M}[S]$

into both a covariant and a contravariant functor from $\mathsf{FinSet}$ to the category of $M$-modules. But it only defines a covariant functor from $\mathsf{Set}$ to the category of $M$-modules, and

$S \mapsto \mathbb{N}^S$

only defines a contravariant functor from $\mathsf{Set}$ to the category of $M$-modules.

It's the covariant functor that's relevant in my paper with Jade. In my paper on reaction networks with Blake and my paper on Markov processes with Kenny it's really important that

$S \mapsto \mathbb{R}[S]$

defines both a covariant and contravariant functor from $\mathsf{FinSet}$ to the category of real vector spaces.

John Baez (Apr 14 2020 at 05:29):

See definition 2.5 here if you're curious:

$\;$

• Coarse-graining open Markov processes.