Quantales from Petri Nets

6 October, 2019

A referee pointed out this paper to me:

• Uffe Engberg and Glynn Winskel, Petri nets as models of linear logic, in Colloquium on Trees in Algebra and Programming, Springer, Berlin, 1990, pp. 147–161.

It contains a nice observation: we can get a commutative quantale from any Petri net.

I’ll explain how in a minute. But first, what does have to do with linear logic?

In linear logic, propositions form a category where the morphisms are proofs and we have two kinds of ‘and’: \& , which is a cartesian product on this category, and \otimes, which is a symmetric monoidal structure. There’s much more to linear logic than this (since there are other connectives), and maybe also less (since we may want our category to be a mere poset), but never mind. I want to focus on the weird business of having two kinds of ‘and’.

Since \& is cartesian we have P \Rightarrow P \& P as usual in logic.

But since \otimes is not cartesian we usually don’t have P \Rightarrow P \otimes P. This other kind of ‘and’ is about resources: from one copy of a thing P you can’t get two copies.

Here’s one way to think about it: if P is “I have a sandwich”, P \& P is like “I have a sandwich and I have a sandwich”, while P \otimes P is like “I have two sandwiches”.

A commutative quantale captures these two forms of ‘and’, and more. A commutative quantale is a commutative monoid object in the category of cocomplete posets: that is, posets where every subset has a least upper bound. But it’s a fact that any cocomplete poset is also complete: every subset has a greatest lower bound!

If we think of the elements of our commutative quantale as propositions, we interpret x \le y as “x implies y”. The least upper bound of any subset of proposition is their ‘or’. Their greatest lower bound is their ‘and’. But we also have the commutative monoid operation, which we call \otimes. This operation distributes over least upper bounds.

So, a commutative quantale has both the logical \& (not just for pairs of propositions, but arbitrary sets of them) and the \otimes operation that describes combining resources.

To get from a Petri net to a commutative quantale, we can compose three functors.

First, any Petri net gives a commutative monoidal category—that is, a commutative monoid object in \mathsf{Cat}. Indeed, my student Jade has analyzed this in detail and shown the resulting functor from the category of Petri nets to the category of commutative monoidal categories is a left adjoint:

• Jade Master, Generalized Petri nets, Section 4.

Second, any category gives a poset where we say x \le y if there is a morphism from x to y. Moreover, the resulting functor \mathsf{Cat} \to \mathsf{Poset} preserves products. As a result, every commutative monoidal category gives a commutative monoidal poset: that is, a commutative monoid object in the category of Posets.

Composing these two functors, every Petri net gives a commutative monoidal poset. Elements are of this poset are markings of the Petri net, the partial order is “reachability”, and the commutative monoid structure is addition markings.

Third, any poset P gives another poset \widehat{P} whose elements are downsets of P: that is, subsets S \subseteq P such that

x \in S, y \le x \; \implies \; y \in S

The partial order on downsets is inclusion. This new poset \widehat{P} is ‘better’ than P because it’s cocomplete. That is, any union of downsets is again a downset. Moreover, \widehat{P} contains P as a sub-poset. The reason is that each x \in P gives a downset

\downarrow x = \{y \in P : \; y \le x \}

and clearly

x \le y \; \iff \;  \downarrow x \subseteq \downarrow y

Composing this third functor with the previous two, every Petri net gives a commutative monoid object in the category of cocomplete posets. But this is just a commutative quantale!

What is this commutative quantale like? Its elements are downsets of markings of our Petri net: sets of markings such that if x is in the set and x is reachable from y then y is also in the set.

It’s good to contemplate this a bit more. A marking can be seen as a ‘resource’. For example, if our Petri net has a place in it called sandwich there is a marking 2sandwich, which means you have two sandwiches. Downsets of markings are sets of markings such that if x is in the set and x is reachable from y then y is also in the set! An example of a downset would be “a sandwich, or anything that can give you a sandwich”. Another is “two sandwiches, or anything that can give you two sandwiches”.

The tensor product \otimes comes from addition of markings, extended in the obvious way to downsets of markings. For example, “a sandwich, or anything that can give you a sandwich” tensored with “a sandwich, or anything that can give you a sandwich” equals “two sandwiches, or anything that can give you two sandwiches”.

On the other hand, the cartesian product \& is the logical ‘and’:
if you have “a sandwich, or anything that can give you a sandwich” and you have “a sandwich, or anything that can give you a sandwich”, then you just have “a sandwich, or anything that can give you a sandwich”.

So that’s the basic idea.


Applied Category Theory Meeting at UCR (Part 2)

30 September, 2019

 

Joe Moeller and I have finalized the schedule of our meeting on applied category theory:

Applied Category Theory, special session of the Fall Western Sectional Meeting of the AMS, U. C. Riverside, Riverside, California, 9–10 November 2019.

It’s going to be really cool, with talks on everything from brakes to bicategories, from quantum physics to social networks, and more—with the power of category theory as the unifying theme!

You can get information on registration, hotels and such here. If you’re coming, you might also want to attend Eugenia Cheng‘s talk on the afternoon of Friday November 8th.   I’ll announce the precise title and time of her talk, and also the location of all the following talks, as soon as I know!

In what follows, the person actually giving the talk has an asterisk by their name. You can click on talk titles to see abstracts of the talks.

Saturday November 9, 2019, 8:00 a.m.-10:50 a.m.

Saturday November 9, 2019, 3:00 p.m.-5:50 p.m.

Sunday November 10, 2019, 8:00 a.m.-10:50 a.m.

Sunday November 10, 2019, 2:00 p.m.-4:50 p.m.


Structured Cospans

1 July, 2019

My grad student Kenny Courser gave a talk at the 4th Symposium on Compositional Structures. He spoke about his work with Christina Vasilakopolou and me. We’ve come up with a theory that can handle a broad class of open systems, from electrical circuits to chemical reaction networks to Markov processes and Petri nets. The idea is to treat open systems as morphisms in a category of a particular kind: a ‘structured cospan category’.

Here is his talk:

• Kenny Courser, Structured cospans.

In July 11th I’m going to talk about structured cospans at the big annual category theory conference, CT2019:

• John Baez, Structured cospans.

I borrowed more than just the title from Kenny’s talk… but since I’m an old guy, they’re giving me time to say more stuff. For full details, try Kenny’s thesis:

• Kenny Courser, The Mathematics of Open Systems from a Double Categorical Perspective.

This thesis is not quite in its final form, so I won’t try to explain it all now. But it’s full of great stuff, so I hope you look at it! If you have any questions or corrections please let us know.

We’ve been working on this project for a couple of years, so there’s a lot to say… but right now let me just tell you what a ‘structured cospan’ is.

Suppose you have any functor L \colon \mathsf{A} \to \mathsf{X}. Then a structured cospan is a diagram like this:

For example if L \colon \mathsf{A} \to \mathsf{X} is the functor from sets to graphs sending each set to the graph with that set of vertices and no edges, a structured cospan looks like this:

It’s a graph with two sets getting mapped into its set of vertices. I call this an open graph. Or if L \colon \mathsf{A} \to \mathsf{X} is the functor from sets to Petri nets sending each set to the Petri having that set of places and nothing else, a structured cospan looks like this:

You can read a lot more about this example here:

• John Baez, Open Petri nets, Azimuth, 15 August 2018.

It illustrates many ideas from the general theory of structured cospans: for example, what we do with them.

You may have heard of a similar idea: ‘decorated cospans’, invented by Brendan Fong. You may wonder what’s the difference!

Kenny’s talk explains the difference pretty well. Basically, decorated cospans that look isomorphic may not be technically isomorphic. For example, if we have an open graph like this:

and its set of edges is \{a,b,c,d\}, this is not isomorphic to the identical-looking open graph whose set of edges is \{b,c,d,e\}. That’s right: the names of the edges matter!

This is an annoying glitch in the formalism. As Kenny’s talk explains, structured cospans don’t suffer from this problem.

My talk at CT2019 explains another way to fix this problem: using a new improved concept of decorated cospan! This new improved concept gives results that match those coming from structured cospan in many cases. Proving this uses some nice theorems proved by Kenny Courser, Christina Vasilakopoulou and also Daniel Cicala.

But I think structured cospans are simpler than decorated cospans. They get the job done more easily in most cases, though they don’t handle everything that decorated cospans do.

I’ll be saying more about structured cospans as time goes on. The basic theorem, in case you’re curious but don’t want to look at my talk, is this:

Theorem. Let \mathsf{A} be a category with finite coproducts, \mathsf{X} a category with finite colimits, and L \colon \mathsf{A} \to \mathsf{X} a functor preserving finite coproducts. Then there is a symmetric monoidal category {}_L \mathsf{Csp}(\mathsf{X}) where:

• an object is an object of \mathsf{A}
• a morphism is an isomorphism class of structured cospans:

Here two structured cospans are isomorphic if there is a commutative diagram of this form:

If you don’t want to work with isomorphism classes of structured cospans, you can use a symmetric monoidal bicategory where the 1-morphisms are actual structured cospans. But following ideas of Mike Shulman, it’s easier to work with a symmetric monoidal double category. So:

Theorem. Let \mathsf{A} be a category with finite coproducts, \mathsf{X} a category with finite colimits, and L \colon \mathsf{A} \to \mathsf{X} a functor preserving finite coproducts. Then there is a symmetric monoidal double category {_L \mathbb{C}\mathbf{sp}(\mathsf{X})} where:

• an object is an object of \mathsf{A}
• a vertical 1-morphism is a morphism of \mathsf{A}
• a horizontal 1-cell is a structured cospan

• a 2-morphism is a commutative diagram


Props in Network Theory (Part 2)

14 May, 2019


Here’s my talk for SYCO4 next week:

Props in network theory.

Abstract. To describe systems composed of interacting parts, scientists and engineers draw diagrams of networks: flow charts, Petri nets, electrical circuit diagrams, signal-flow graphs, chemical reaction networks, Feynman diagrams and the like. All these different diagrams fit into a common framework: the mathematics of symmetric monoidal categories. Two complementary approaches are presentations of props using generators and relations (which are more algebraic in flavor) and structured cospan categories (which are more geometrical). In this talk we focus on the former. A “prop” is a strict symmetric monoidal category whose objects are tensor powers of a single generating object. We will see that props are a flexible tool for describing many kinds of networks.

You can read a lot more here:

• John Baez, Props in network theory (part 1), Azimuth, April 27, 2018.


The Pi Calculus: Towards Global Computing

4 April, 2019

 

Check out the video of Christian Williams’’s talk in the Applied Category Theory Seminar here at U. C. Riverside. It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

Abstract. Historically, code represents a sequence of instructions for a single machine. Each computer is its own world, and only interacts with others by sending and receiving data through external ports. As society becomes more interconnected, this paradigm becomes more inadequate – these virtually isolated nodes tend to form networks of great bottleneck and opacity. Communication is a fundamental and integral part of computing, and needs to be incorporated in the theory of computation.

To describe systems of interacting agents with dynamic interconnection, in 1980 Robin Milner invented the pi calculus: a formal language in which a term represents an open, evolving system of processes (or agents) which communicate over names (or channels). Because a computer is itself such a system, the pi calculus can be seen as a generalization of traditional computing languages; there is an embedding of lambda into pi – but there is an important change in focus: programming is less like controlling a machine and more like designing an ecosystem of autonomous organisms.

We review the basics of the pi calculus, and explore a variety of examples which demonstrate this new approach to programming. We will discuss some of the history of these ideas, called “process algebra”, and see exciting modern applications in blockchain and biology.

“… as we seriously address the problem of modelling mobile communicating systems we get a sense of completing a model which was previously incomplete; for we can now begin to describe what goes on outside a computer in the same terms as what goes on inside – i.e. in terms of interaction. Turning this observation inside-out, we may say that we inhabit a global computer, an informatic world which demands to be understood just as fundamentally as physicists understand the material world.” — Robin Milner

The talks slides are here.

Reading material:

• Robin Milner, The polyadic pi calculus: a tutorial.

• Robin Milner, Communicating and Mobile Systems.

• Joachim Parrow, An introduction to the pi calculus.


Social Contagion Modeled on Random Networks

29 March, 2019

 

Check out the video of Daniel Cicala’s talk, the fourth in the Applied Category Theory Seminar here at U. C. Riverside. It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

Abstract. A social contagion may manifest as a cultural trend, a spreading opinion or idea or belief. In this talk, we explore a simple model of social contagion on a random network. We also look at the effect that network connectivity, edge distribution, and heterogeneity has on the diffusion of a contagion.

The talk slides are here.

Reading material:

• Mason A. Porter and James P. Gleeson, Dynamical systems on networks: a tutorial.

• Duncan J. Watts, A simple model of global cascades on random networks.


Complex Adaptive System Design (Part 9)

24 March, 2019

Here’s our latest paper for the Complex Adaptive System Composition and Design Environment project:

• John Baez, John Foley and Joe Moeller, Network models from Petri nets with catalysts.

Check it out! And please report typos, mistakes, or anything you have trouble understanding! I’m happy to answer questions here.

The idea

Petri nets are a widely studied formalism for describing collections of entities of different types, and how they turn into other entities. I’ve written a lot about them here. Network models are a formalism for designing and tasking networks of agents, which our team invented for this project. Here we combine these ideas! This is worthwhile because while both formalisms involve networks, they serve a different function, and are in some sense complementary.

A Petri net can be drawn as a bipartite directed graph with vertices of two kinds: places, drawn as circles, and transitions drawn as squares:

When we run a Petri net, we start by placing a finite number of dots called tokens in each place:

This is called a marking. Then we repeatedly change the marking using the transitions. For example, the above marking can change to this:

and then this:

Thus, the places represent different types of entity, and the transitions are ways that one collection of entities of specified types can turn into another such collection.

Network models serve a different function than Petri nets: they are a general tool for working with networks of many kinds. Mathematically a network model is a lax symmetric monoidal functor G \colon \mathsf{S}(C) \to \mathsf{Cat}, where \mathsf{S}(C) is the free strict symmetric monoidal category on a set C. Elements of C represent different kinds of ‘agents’. Unlike in a Petri net, we do not usually consider processes where these agents turn into other agents. Instead, we wish to study everything that can be done with a fixed collection of agents. Any object x \in \mathsf{S}(C) is of the form c_1 \otimes \cdots \otimes c_n for some c_i \in C; thus, it describes a collection of agents of various kinds. The functor G maps this object to a category G(x) that describes everything that can be done with this collection of agents.

In many examples considered so far, G(x) is a category whose morphisms are graphs of some sort whose nodes are agents of types c_1, \dots, c_n. Composing these morphisms corresponds to ‘overlaying’ graphs. Network models of this sort let us design networks where the nodes are agents and the edges are communication channels or shared commitments. In our first paper the operation of overlaying graphs was always commutative:

• John Baez, John Foley, Joe Moeller and Blake Pollard, Network models.

Subsequently Joe introduced a more general noncommutative overlay operation:

• Joe Moeller, Noncommutative network models.

This lets us design networks where each agent has a limit on how many communication channels or commitments it can handle; the noncommutativity lets us take a ‘first come, first served’ approach to resolving conflicting commitments.

Here we take a different tack: we instead take G(x) to be a category whose morphisms are processes that the given collection of agents, x, can carry out. Composition of morphisms corresponds to carrying out first one process and then another.

This idea meshes well with Petri net theory, because any Petri net P determines a symmetric monoidal category FP whose morphisms are processes that can be carried out using this Petri net. More precisely, the objects in FP are markings of P, and the morphisms are sequences of ways to change these markings using transitions, e.g.:

Given a Petri net, then, how do we construct a network model G \colon \mathsf{S}(C) \to \mathsf{Cat}, and in particular, what is the set C? In a network model the elements of C represent different kinds of agents. In the simplest scenario, these agents persist in time. Thus, it is natural to take C to be some set of ‘catalysts’. In chemistry, a reaction may require a catalyst to proceed, but it neither increases nor decrease the amount of this catalyst present. In everyday life, a door serves as a catalyst: it lets you walk though a wall, and it doesn’t get used up in the process!

For a Petri net, ‘catalysts’ are species that are neither increased nor decreased in number by any transition. For example, in the following Petri net, species a is a catalyst:

but neither b nor c is a catalyst. The transition \tau_1 requires one token of type a as input to proceed, but it also outputs one token of this type, so the total number of such tokens is unchanged. Similarly, the transition \tau_2 requires no tokens of type a as input to proceed, and it also outputs no tokens of this type, so the total number of such tokens is unchanged.

In Theorem 11 of our paper, we prove that given any Petri net P, and any subset C of the catalysts of P, there is a network model

G \colon \mathsf{S}(C) \to \mathsf{Cat}

An object x \in \mathsf{S}(C) says how many tokens of each catalyst are present; G(x) is then the subcategory of FP where the objects are markings that have this specified amount of each catalyst, and morphisms are processes going between these.

From the functor G \colon \mathsf{S}(C) \to \mathsf{Cat} we can construct a category \int G by ‘gluing together’ all the categories G(x) using the Grothendieck construction. Because G is symmetric monoidal we can use an enhanced version of this construction to make \int G into a symmetric monoidal category. We already did this in our first paper on network models, but by now the math has been better worked out here:

• Joe Moeller and Christina Vasilakopoulou, Monoidal Grothendieck construction.

The tensor product in \int G describes doing processes ‘in parallel’. The category \int G is similar to FP, but it is better suited to applications where agents each have their own ‘individuality’, because FP is actually a commutative monoidal category, where permuting agents has no effect at all, while \int G is not so degenerate. In Theorem 12 of our paper we make this precise by more concretely describing \int G as a symmetric monoidal category, and clarifying its relation to FP.

There are no morphisms between an object of G(x) and an object of G(x') when x \not\cong x', since no transitions can change the amount of catalysts present. The category FP is thus a ‘disjoint union’, or more technically a coproduct, of subcategories FP_i where i, an element of free commutative monoid on C, specifies the amount of each catalyst present.

The tensor product on FP has the property that tensoring an object in FP_i with one in FP_j gives an object in FP_{i+j}, and similarly for morphisms. However, in Theorem 14 we show that each subcategory FP_i also has its own tensor product, which describes doing one process after another while reusing catalysts.

This tensor product is a very cool thing. On the one hand it’s quite obvious: for example, if two people want to walk through a door, they can both do it, one at a time, because the door doesn’t get used up when someone walks through it. On the other hand, it’s mathematically interesting: it turns out to give, not a monoidal category, but something called a ‘premonoidal’ category. This concept, which we explain in our paper, was invented by John Power and Edmund Robinson for use in theoretical computer science.

The paper has lots of pictures involving jeeps and boats, which serve as catalysts to carry people first from a base to the shore and then from the shore to an island. I think these make it clear that the underlying ideas are quite commonsensical. But they need to be formalized to program them into a computer—and it’s nice that doing this brings in some classic themes in category theory!


Some posts in this series:

Part 1. CASCADE: the Complex Adaptive System Composition and Design Environment.

Part 2. Metron’s software for system design.

Part 3. Operads: the basic idea.

Part 4. Network operads: an easy example.

Part 5. Algebras of network operads: some easy examples.

Part 6. Network models.

Part 7. Step-by-step compositional design and tasking using commitment networks.

Part 8. Compositional tasking using category-valued network models.

Part 9 – Network models from Petri nets with catalysts.