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: deprecated: chemistry

Topic: invariants of Petri nets

Benjamin Merlin Bumpus (he/him) (Jun 21 2022 at 15:04):

A thought stemming from our work on additive invariants on open petri nets (which could possibly be a follow-up paper) is that we really should think about pushout-preserving functors to $\mathbb{N}_\leq$ or to $\mathbf{FinSet}$. Since there will be many more such functors in these cases.

For open graphs where the interfaces are cliques, there should be uncountably-many such functors to $\mathbb{N}_\leq$ (I'm saying this based on my paper with Z. Kocsis and based on this paper by R. Halin). So I suspect that the situation gets more interesting for open petri nets as well.

All of this is also not even mentioning that most of the (graph-theoretically) interesting functors from $\mathbf{Grph}$ to $\mathbf{FinSet}$ aren't even pushout-preserving... so there's probably a whole other world to explore there even for Petri nets!

John Baez (Jun 21 2022 at 15:32):

This is neat. Invariants (functors) are useful when they are powerful (close to faithful) and easy to compute, but these two properties tend to conflict each other. So it's nice to explore the world of invariants of open Petri nets that are more powerful but a bit harder to compute than functors to $\mathsf{B} \mathbb{N}$.

John Baez (Jun 21 2022 at 15:36):

Having "uncountably" many functors is not necessarily as amazing as it sounds, since there are uncountably many functions from $\mathbb{N}$ to $\{T,F\}$, but in some sense they're all "generated" from the functions that take the value $T$ at one number and $F$ at all others.

John Baez (Jun 21 2022 at 15:37):

("Some sense": for example, these functions form a Boolean algebra, which is generated as a Boolean algebra by the characteristic functions of singletons.)

Benjamin Merlin Bumpus (he/him) (Jun 21 2022 at 15:50):

Hmm, yes, that's a good point.
In think that something living between (in terms of `complexity') $\mathbf{B}\mathbb{N}$ and $\mathbf{N}_\leq$ should be a good place to look

Benjamin Merlin Bumpus (he/him) (Jun 21 2022 at 15:52):

Although, in relation to your second point, I know that, for Graphs whose interfaces are cliques, the maxing functors are quite interesting (they include stuff like the Hadwiger number, modified chromatic number and modified connectivity number).

Benjamin Merlin Bumpus (he/him) (Jun 21 2022 at 15:53):

so I'm guessing that, by analogy, there would probably be also a fair amount of structure that would crop-up in Petri nets for similar functors?

Sam Tenka (Jun 21 2022 at 18:23):

John Baez said:

("Some sense": for example, these functions form a Boolean algebra, which is generated as a Boolean algebra by the characteristic functions of singletons.)

Nitpick: we probably want to say "complete lattice" instead of "boolean algebra", since the latter just have finitary operations. Said another way, those indicator functions generate the sub-algebra of all finite and all cofinite support functions rather than the full algebra of all functions.

Sam Tenka (Jun 21 2022 at 18:37):

Benjamin Merlin Bumpus said:

A thought stemming from our work on additive invariants on open petri nets (which could possibly be a follow-up paper) is that we really should think about pushout-preserving functors to $\mathbb{N}_\leq$ or to $\mathbf{FinSet}$. Since there will be many more such functors in these cases.

Pushout preservation is a pretty strong condition. For example, we can build any closed petri net by starting with connected closed petri nets with one or zero transitions and taking pushouts along sets (i.e. transitionless closed petri nets). But finite sets themselves are either empty or are pushouts of smaller finite sets along an empty set.

Thus, a class function from ClosedPetri to N-as-a-poset that sends pushouts to pushouts is determined by where it sends the empty set, the singleton set, and connected closed petri nets with exactly one transition. I think this gives us another classification theorem of the form "every such class function sends a closed petri net to max ( b, max (instead of sum) over a_i ), where i ranges through the degree-labeled transitions present in the closed petri net ". Here, b and the countably many a_i are freely chooseable natural numbers.

John Baez (Jun 21 2022 at 22:41):

Sam Tenka said:

John Baez said:

("Some sense": for example, these functions form a Boolean algebra, which is generated as a Boolean algebra by the characteristic functions of singletons.)

Nitpick: we probably want to say "complete lattice" instead of "boolean algebra", since the latter just have finitary operations.

Yes you're right... I secretly meant "complete Boolean algebra".

Benjamin Merlin Bumpus (he/him) (Jun 22 2022 at 07:53):

Sam Tenka said:

Benjamin Merlin Bumpus said:

A thought stemming from our work on additive invariants on open petri nets (which could possibly be a follow-up paper) is that we really should think about pushout-preserving functors to $\mathbb{N}_\leq$ or to $\mathbf{FinSet}$. Since there will be many more such functors in these cases.

Pushout preservation is a pretty strong condition. For example, we can build any closed petri net by starting with connected closed petri nets with one or zero transitions and taking pushouts along sets (i.e. transitionless closed petri nets). But finite sets themselves are either empty or are pushouts of smaller finite sets along an empty set.

Thus, a class function from ClosedPetri to N-as-a-poset that sends pushouts to pushouts is determined by where it sends the empty set, the singleton set, and connected closed petri nets with exactly one transition. I think this gives us another classification theorem of the form "every such class function sends a closed petri net to max ( b, max (instead of sum) over a_i ), where i ranges through the degree-labeled transitions present in the closed petri net ". Here, b and the countably many a_i are freely chooseable natural numbers.

I agree with what you said. However, I should point out that I was handvawing a bit earlier: for the case of graphs, you get lots of interesting functors if you have the following set-up:
-- you are looking at functors of the form $F: \mathbf{Grph}_{mono} \to \mathbb{N}_\leq$ where $\mathbf{Grph}_{mono}$ is the category of graphs and and monomorphisms
-- rather than being pushout preserving (since $\mathbf{Grph}_{mono}$ doesn't have pushouts) , $F$ is required to be proxy-pushout preserving whenever we take proxy-pushouts over complete graphs.

(Another note, I tend to gravitate to thinking about the "closed" version of things for these kinds of questions. This has to do with what we discussed last week in our meeting: in the monic "open" case we get the "accidental" left-and-right private-node functors $\mathcal{L}$ and $\mathcal{R}$ which are pretty much just a by-product of the choice of cospan and hence not really a feature of the Petri net itself... Does that make sense? I'm not yet caffeinated, and I feel like I explained this better last week :rolling_on_the_floor_laughing: )

(P.S. Zoltan and I introduced proxy-pushouts in the paper I linked and, as I recently found-out, @Matthew Di Meglio adopted this terminology in Cpt. 3 of his thesis (and he does lots of cool stuff with it!); so, if you're interested, you can read a bit about what a proxy-pushout is in either of these.)

Sam Tenka (Jun 22 2022 at 15:02):

Excited to learn more about this from you! Haven't yet had time or caffeine myself to digest.
Note: in the result written in the chemistry subgroup, we find a whole bunch of "accidental" functors related to the left and right private node functors. Though accidental, they are interersting!

Benjamin Merlin Bumpus (he/him) (Jun 23 2022 at 07:49):

oh, yes, I agree, they are definitely interesting since they describe invariants that are inherent to the "openness" :smile:
all I meant to say is that I think it's a good idea to study both kinds (from "open" and "closed" worlds) independently.. but simultaneously.

Benjamin Merlin Bumpus (he/him) (Jun 24 2022 at 09:35):

Yesterday @Sam Tenka, @Layla, @Jordy Lopez Garcia and I had a rather satisfying meeting in which we essentially finished off all of the remaining cases of the "additive invariants of Petri nets" project (which we'll write-up soon and share with the rest of you :smile: ).

Anyway, one big take-away for me was that, in both the "regular" and the monic cases, the additive invariants seem to be generated by two families $\mathcal{F}_{\mathbf{Set}}$ and $\mathcal{F}_{\mathbf{Petri}}$ of functors.

The first family -- $\mathcal{F}_{\mathbf{Set}}$ -- consists of all the functors that generate (as linear combinations) the additive invariants $\mathbf{Csp}(\mathbf{FinSet}) \to \mathbf{B}\mathbb{N}$.

The second family -- $\mathcal{F}_{\mathbf{Petri}}$ -- consists of the functors which generate (as linear combinations) the following class of functors: those of the form $\mathbf{Petri} \to \mathbf{B}\mathbb{N}$ which are "additive over pushouts".

There's probably a slicker way to write this second condition, but I'm running late for a meeting, so I'll have to just think about it later.

Anyway, these observations make me wonder whether something like the situation above is always is the case. What I mean is, suppose I decorate a cospan category $\mathbf{Csp}(\mathbf{C})$ with objects form some category $\mathbf{D}$; is it true that the additive invariants from this decorated cospan category are always going to be generated by two families which respectively generate the "additive" invariants $\mathbf{Csp}(\mathbf{C}) \to \mathbf{B}\mathbb{N}$ and the "additive-over-pushout"-invariants from $\mathbf{D}$?

I suspect that this naïve conjecture isn't true in general, but I do think that some better reformulation of the conjecture is indeed true..

Anyway, I find this pretty exciting :tada: .. but I'm late for my meeting, so bye! :wave:

John Baez (Jun 24 2022 at 17:25):

Benjamin Merlin Bumpus said:

Yesterday Sam Tenka, Layla, Jordy Lopez Garcia and I had a rather satisfying meeting in which we essentially finished off all of the remaining cases of the "additive invariants of Petri nets" project (which we'll write-up soon and share with the rest of you :smile: ).

Anyway, one big take-away for me was that, in both the "regular" and the monic cases, the additive invariants seem to be generated by two families $\mathcal{F}_{\mathbf{Set}}$ and $\mathcal{F}_{\mathbf{Petri}}$ of functors.

The first family -- $\mathcal{F}_{\mathbf{Set}}$ -- consists of all the functors that generate (as linear combinations) the additive invariants $\mathbf{Csp}(\mathbf{FinSet}) \to \mathbf{B}\mathbb{N}$.

The second family -- $\mathcal{F}_{\mathbf{Petri}}$ -- consists of the functors which generate (as linear combinations) the following class of functors: those of the form $\mathbf{Petri} \to \mathbf{B}\mathbb{N}$ which are "additive over pushouts".

There's probably a slicker way to write this second condition, but I'm running late for a meeting, so I'll have to just think about it later.

Anyway, these observations make me wonder whether something like the situation above is always is the case. What I mean is, suppose I decorate a cospan category $\mathbf{Csp}(\mathbf{C})$ with objects from some category $\mathbf{D}$; is it true that the additive invariants from this decorated cospan category are always going to be generated by two families which respectively generate the "additive" invariants $\mathbf{Csp}(\mathbf{C}) \to \mathbf{B}\mathbb{N}$ and the "additive-over-pushout"-invariants from $\mathbf{D}$?

Something like that would be really cool. If you're doing decorated cospans I suspect the answer has to depend on the functor used to define the decorated cospan category, which recall is a lax monoidal pseudofunctor $F: \mathsf{C} \to \mathbf{Cat}$.

John Baez (Jun 24 2022 at 17:27):

When you talk about "decorating with objects from some category $\mathsf{D}$, it sounds like you're really talking about structured cospans: setting up a structured cospans category involves a left adjoint $L : \mathsf{C} \to \mathsf{D}$.

John Baez (Jun 24 2022 at 17:27):

In this case I feel the answer to your question of "classifying all the additive invariants" must involve not just $\mathsf{D}$ but also the functor $L : \mathsf{C} \to \mathsf{D}$.

John Baez (Jun 24 2022 at 17:28):

But anyway, maybe carefully handling the case of Petri nets will give you a better feeling for these more general questions.