Linear Logic and Petri Nets

28 July, 2020

Wow! Elena Di Lavore and Xiaoyan Li explained how to make a category of Petri nets that’s a model of linear logic! I consider myself a sort of expert on Petri nets, but I didn’t know this stuff:

• Elena Di Lavore and Xiaoyan Li, Linear logic flavoured composition of Petri nets, The n-Category Café, 27 July 2020.

It has great pictures, too. Let me summarize a tiny bit.

A Petri net is a very simple thing. Here’s a Petri net that shows how healthy white blood cells (H), individual viruses (V) and infected white blood cells (I) interact when someone gets AIDS:

The yellow boxes are different kinds of things, called species; the aqua boxes are processes, called transitions.

There are different ways to form categories using Petri nets. Jade Master and I have focused on two:

1) How to turn a Petri net into a category where the morphisms say what the Petri net can do.

2) How to make a category with ‘open’ Petri nets as morphisms. Composing these lets you build big Petri nets from smaller pieces.

open_petri_2

Di Lavore and Li instead explain:

3) How to make a category with elementary Petri nets as objects: a morphism from one elementary Petri net to another turns each transition of the first into a transition of the second.

An elementary Petri net is one where each transition uses each species at most once as an input and at most once as an output:

nets

The category they get has lots of interesting structure! Like products, shown here:

product

In fact it has products, coproducts, two other monoidal structures, and exponentials—all fitting together in a wonderful way, as described by intuitionistic linear logic! To prove this, the key is to use Valeria de Paiva’s work on “Dialectica categories”. They explain how.

This is not original research: Elena Di Lavore and Xiaoyan Li wrote this blog article for the ACT2020 Adjoint School, and they’re explaining Carolyn Brown and Doug Gurr’s paper “A categorical linear framework for Petri nets”.

It’s worth comparing this paper:

• 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.

Engberg and Winskel get a model of linear logic—or to be precise, a ‘commutative quantale’—by taking the category you get from a single Petri net as in item 1) and massaging it a bit. I explained it here:

• John Baez, Quantales from Petri nets, Azimuth, 6 October 2019.


A Localic Approach to Dependency, Conflict, and Concurrency

28 April, 2020

In the fifth talk of the ACT@UCR seminar, Gershom Bazerman told how to use locales to study the semantics of dependency, conflict, and concurrency.

Afterwards we discussed his talk at the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.2029th.3A.20Gershom.20Bazerman

You can view or join the conversation there if you sign in.

You can see his slides here, or download a video here, or watch the video here:

• Gershom Bazerman, A localic approach to the semantics of dependency, conflict, and concurrency.

Abstract. Petri nets have been of interest to applied category theory for some time. Back in the 1980s, one approach to their semantics was given by algebraic gadgets called “event structures.” We use classical techniques from order theory to study event structures without conflict restrictions (which we term “dependency structures with choice”) by their associated “traces”, which let us establish a one-to-one correspondence between DSCs and a certain class of locales. These locales have an internal logic of reachability, which can be equipped with “versioning” modalities that let us abstract away certain unnecessary detail from an underlying DSC. With this in hand we can give a general notion of what it means to “solve a dependency problem” and combinatorial results bounding the complexity of this. Time permitting, I will sketch work-in-progress which hopes to equip these locales with a notion of conflict, letting us capture the full semantics of general event structures in the form of homological data, thus providing one avenue to the topological semantics of concurrent systems. This is joint work with Raymond Puzio.


The Monoidal Grothendieck Construction

24 April, 2020

My student Joe Moeller gave a talk at the MIT Categories Seminar today! People discussed his talk at the Category Theory Community Server, and if you join that you can see the discussion here:

https://categorytheory.zulipchat.com/#narrow/stream/229457-MIT-Categories.20Seminar/topic/April.2023.20-.20Joe.20Moeller’s.20talk

You can see his slides here, and watch a video of his talk here:

The monoidal Grothendieck construction

Abstract. The Grothendieck construction gives an equivalence between fibrations and indexed categories. We will begin with a review of the classical story. We will then lift this correspondence to two monoidal variants, a global version and a fibre-wise version. Under certain conditions these are equivalent, so one can transfer fibre-wise monoidal structures to the total category. We will give some examples demonstrating the utility of this construction in applied category theory and categorical algebra.

The talk is based on this paper:

• Joe Moeller and Christina Vasilakopoulou, Monoidal Grothendieck construction.

This, in turn, had its roots in our work on network models, a setup for the compositional design of networked systems:

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


Star-Autonomous Envelopes

21 April, 2020

Shulman_slide

In the fourth talk of the ACT@UCR seminar, Michael Shulman told us how to create nice string diagams for any closed symmetric monoidal category.

Mike had to teach right after his talk, but he rejoined us for discussions later at the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.2022nd.3A.20Michael.20Shulman

You can view or join the conversation there if you sign in.

You can see his slides here, or download a video of his talk here, or watch the video here:

• April 22, Michael Shulman, Star-autonomous envelopes.

Abstract. Symmetric monoidal categories with duals, a.k.a. compact monoidal categories, have a pleasing string diagram calculus. In particular, any compact monoidal category is closed with [A,B] = (A* ⊗ B), and the transpose of A ⊗ B → C to A → [B,C] is represented by simply bending a string. Unfortunately, a closed symmetric monoidal category cannot even be embedded fully-faithfully into a compact one unless it is traced; and while string diagram calculi for closed monoidal categories have been proposed, they are more complicated, e.g. with “clasps” and “bubbles”. In this talk we obtain a string diagram calculus for closed symmetric monoidal categories that looks almost like the compact case, by fully embedding any such category in a star-autonomous one (via a functor that preserves the closed structure) and using the known string diagram calculus for star-autonomous categories. No knowledge of star-autonomous categories will be assumed.

His talk is based on this paper:

• Michael Shulman, Star-autonomous envelopes.

This subject is especially interesting to me since Mike Stay and I introduced string diagrams for closed monoidal categories in a somewhat ad hoc way in our Rosetta Stone paper—but the resulting diagrams required clasps and bubbles:


beta_reduction

This is the string diagram for beta reduction in the cartesian closed category coming from the lambda calculus.


Structured Cospans and Petri Nets

6 April, 2020

\;

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.

I gave this second talk at the MIT Categories Seminar. People discussed the talk at the Category Theory Community Server.

You can see the slides here and watch a video 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.

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.

I’ve blogged about open Petri nets before, and these articles might be a good way to start learning about them:

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.


Structured Cospans and Double Categories

31 March, 2020

 \; \phantom{a}

This talk on structured cospans and double categories is the first of a two-part series; the second part is about structured cospans and Petri nets.

I gave the first talk at the ACT@UCR seminar, on Wednesday April 1st. Afterwards we discussed it on the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.201st.3A.20John.20Baez

You can view or join the conversation there if you sign in.

You can see my slides here, or download a video here, or watch the video here:

Structured cospans and double categories

Abstract. One goal of applied category theory is to better understand networks appearing throughout science and engineering. Here we introduce “structured cospans” as a way to study networks with inputs and outputs. Given a functor L: A → X, a structured cospan is a diagram in X of the form

If A and X have finite colimits and L is a left adjoint, we obtain a symmetric monoidal category whose objects are those of A and whose morphisms are certain equivalence classes of structured cospans. However, this arises from a more fundamental structure: a symmetric monoidal double category where the horizontal 1-cells are structured cospans, not equivalence classes thereof. We explain the mathematics and illustrate it with an example from epidemiology.

This talk was based on work with Kenny Courser and Christina Vasilakopoulou, some of which appears here:

• John Baez and Kenny Courser, Structured cospans.

• Kenny Courser, Open Systems: a Double Categorical Perspective.

Yesterday Rongmin Lu told me something amazing: structured cospans were invented in 2007 by José Luiz Fiadeiro and Vincent Schmit. It’s pretty common for simple ideas to be discovered several times. The amazing thing is that these other authors also called these things ‘structured cospans’!

• José Luiz Fiadeiro and Vincent Schmitt, Structured co-spans: an algebra of interaction protocols, in International Conference on Algebra and Coalgebra in Computer Science, Springer, Berlin, 2007.

These earlier authors did not do everything we’ve done, so I’m not upset. Their work proves I chose the right name.


Applied Category Theory 2020 (Part 2)

23 March, 2020

Due to the coronavirus outbreak, many universities are moving activities online. This is a great opportunity to open up ACT2020 to a broader audience, with speakers from around the world.

The conference will take place July 6-10 online, coordinated by organizers in Boston USA. Each day there will be around six hours of live talks, which will be a bit more spaced out than usual to accommodate the different time zones of our speakers. All the talks will be both live streamed and recorded on YouTube. We will also have chat rooms and video chats in which participants can discuss various themes in applied category theory.

We will give more details as they become available and post updates on our official webpage:

http://act2020.mit.edu

Since there is no need to book travel, we were able to postpone the acceptance notification, and hence the submission deadline. If you would like to speak, please prepare an abstract or a conference paper according to the instructions here:

http://act2020.mit.edu/#papers

Important dates (all in 2020)

• Submission of contributed papers: May 10
• Acceptance/Rejection notification: June 7
• Tutorial day: July 5
• Main conference: July 6-10

Registration will now be free; please register for the conference ahead of time here:

http://act2020.mit.edu/#registration

We will send registering participants links to the live stream, the recordings, and the chat rooms, and we’ll use the list to inform participants of any changes.

Submissions

To give a talk at ACT2020, you have to submit a paper. You can submit either original research papers or extended abstracts of work submitted/accepted/published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume.

Here’s how to submit papers. Two types of submissions are accepted, which will be reviewed to the same standards:

Proceedings Track. Original contributions of high quality work consisting of a 5–12 page extended abstract that provides evidence for results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submissions of works in progress are encouraged, but must be more substantial than a research proposal.

Non-Proceedings Track. Descriptions of high-quality work submitted or published elsewhere will also be considered, provided the work is recent and relevant to the conference. The work may be of any length, but the program committee members may only look at the first 3 pages of the submission, so you should ensure these pages contain sufficient evidence of the quality and rigor of your work.

Submissions should be prepared using LaTeX, and must be submitted in PDF format. Submission is currently open, and can be perfomed at the following web page:

https://easychair.org/conferences/?conf=act2020

One or more best paper awards may be given out at the discretion of the PC chairs. Selected contributions will be offered extended keynote slots in the program.

Organizers

Here are the local organizers:

• Destiny Chen (administration)
• Brendan Fong
• David Jaz Myers (logistics)
• Paolo Perrone (publicity)
• David Spivak

Here is the committee running the school:

• Carmen Constantin
• Eliana Lorch
• Paolo Perrone

Here is the steering committee:

• John Baez
• Bob Coecke
• David Spivak
• Christina Vasilakopoulou

Here is the program committee:

• Mathieu Anel, CMU
• John Baez, University of California, Riverside
• Richard Blute, University of Ottawa
• Tai-Danae Bradley, City University of New York
• Andrea Censi, ETC Zurich
• Bob Coecke, University of Oxford
• Valeria de Paiva, Samsung Research America and University of Birmingham
• Ross Duncan, University of Strathclyde
• Eric Finster, University of Birmingham
• Brendan Fong, Massachusetts Institute of Technology
• Tobias Fritz, Perimeter Institute for Theoretical Physics
• Richard Garner, Macquarie University
• Fabrizio Romano Genovese, Statebox
• Amar Hadzihasanovic, IRIF, Université de Paris
• Helle Hvid Hansen, Delft University of Technology
• Jules Hedges, Max Planck Institute for Mathematics in the Sciences
• Kathryn Hess Bellwald, Ecole Polytechnique Fédérale de Lausanne
• Chris Heunen, The University of Edinburgh
• Joachim Kock, UAB
• Tom Leinster, The University of Edinburgh
• Martha Lewis, University of Amsterdam
• Daniel R. Licata, Wesleyan University
• David Jaz Myers, Johns Hopkins University
• Paolo Perrone, MIT
• Vaughan Pratt, Stanford University
• Peter Selinger, Dalhousie University
• Michael Shulman, University of San Diego
David I. Spivak, MIT (co-chair)
• Walter Tholen, York University
• Todd Trimble, Western Connecticut State University
Jamie Vicary, University of Birmingham (co-chair)
• Maaike Zwart, University of Oxford


Applied Category Theory at NIST (Part 3)

22 February, 2020

Sadly, this workshop has been cancelled due to the coronavirus pandemic. It may be postponed to a later date.

My former student Blake Pollard is working at the National Institute of Standards and Technology. He’s working with Spencer Breiner and Eswaran Subrahmanian, who are big advocates of using category theory to organize design and manufacturing processes. In the spring of 2018 they had a workshop on applied category theory with a lot of honchos from industry and government in attendance—you can see videos by clicking the link.

This spring they’re having another workshop on this topic!

Applied Category Theory Workshop, April 8-9, 2020, National Institute of Standards and Technology, Gaithersburg, Maryland. Organized by Spencer Breiner, Blake Pollard and Eswaran Subrahmanian.

The focus of this workshop in on fostering the development of tooling and use-cases supporting the applied category theory community. We are particularly interested in bringing together practitioners who are engaged with susceptible domains as well as those involved in the implementation, support, and utilization of software and other tools. There will be a number of talks/demos showcasing existing approaches as well as ample time for discussion.

Here are the speakers listed so far:

• John Baez, University of California, Riverside

• Arquimedes Canedo, Siemens

• Daniel Cicala, New Haven University

• James Fairbanks, Georgia Tech Research Institute

• Jules Hedges, Max Planck Institute for the Mathematical Sciences

• Jelle Herold, Statebox

• Evan Patterson, Stanford University

• Qunfen Qi, University of Huddersfield

• Christian Williams, University of California, Riverside

• Ryan Wisnesky, Conexus.ai

I’ll also be giving a separate talk on “ecotechnology” at NIST on Friday April 10th; more about that later!


Applied Category Theory 2020 — Adjoint School

23 December, 2019

Boston2

Like last year and the year before, there will be a school associated to this year’s international conference on applied category theory! If you’re trying to get into applied category theory, this is the best possible way.

Applied Category Theory 2020 — Adjoint School.

The school will consist of online meetings from February to June 2020, followed by a research week June 29–July 3, 2020 at MIT in Cambridge Massachusetts. The conference follows on July 6–10, 2020, and if you attend the school you should also go to the conference.

The deadline to apply is January 15 2020; apply here.

There will be 4 mentors teaching courses at the school:

• Michael Johnson, Categories of maintainable relations.

• Nina Otter, Diagrammatic and algebraic approaches to distances between persistence modules.

• Valeria de Paiva, Dialectica categories of Petri nets.

• Michael Shulman, A practical type theory for symmetric monoidal categories.

Click on the links for more detailed information!

Who should apply?

Anyone, from anywhere in the world, who is interested in applying category-theoretic methods to problems outside of pure mathematics. This is emphatically not restricted to math students, but one should be comfortable working with mathematics. Knowledge of basic category-theoretic language—the definition of monoidal category for example—is encouraged.

We will consider advanced undergraduates, PhD students, post-docs, as well as people working outside of academia. Members of minorities, and of any groups which are underrepresented in the mathematics and computer science communities, are especially encouraged to apply.

Structure of the school

Every participant will be assigned to one of the groups above, according to their preference (and to the availability of places within the groups). Each group will consist of a mentor, a TA, and 4-5 students.

Online meetings

Between February and June 2020 there will be an online reading seminar. Each group will have a reading list of two papers, which they will study, and then present to the rest of the school during weekly online meetings. Every member of the school is encouraged to take part in the discussion of every paper, first during the meeting via live chat, and then, in written form, on an online forum. After the presentation and the forum discussion the students of each group will write a blog post about their assigned paper on the n-Category Café.

During this period, the TAs will be there to help the students, answer any question they might have, and moderate the discussions. This way, all the participants will build the necessary background to take part in the research activities during the week at MIT.

Research week

After the online meetings, there will be a two-week event at MIT, from June 29th to July 10th 2020. The first week is dedicated exclusively to the participants of the school. They will work in groups on the research projects outlined above, led by their mentors, with the help of their TAs.

During the second week the ACT 2020 Conference will take place, which is open to a wider audience. The member of each group of the school will have the possibility to present their activity to the audience of the conference, and share their ideas. The conference is not technically part of the school, but is about very similar topics, and participation is very much encouraged. The online meetings should prepare students to be able to follow some of the conference presentations to a reasonable degree, and introduce them to the main problems and techniques of the field.

Questions?

For any questions or doubts please write us at the address act adjoint school at gmail dot com.

Organizers

Carmen Constantin

Eliana Lorch

Paolo Perrone


Applied Category Theory Meeting at UCR (Part 3)

15 November, 2019

 

We had a special session on applied category theory here at UCR:

Applied category theory, Fall Western Sectional Meeting of the AMS, 9–10 November 2019, U.C. Riverside.

I was bowled over by the large number of cool ideas. I’ll have to blog about some of them. A bunch of people stayed for a few days afterwards, and we had lots of great conversations.

The biggest news was that Brendan Fong and David Spivak definitely want to set up an applied category theory in the San Francisco Bay Area, which they’re calling the Topos Institute. They are now in the process of raising funds for this institute! I plan to be involved, so I’ll be saying more about this later.

But back to the talks. We didn’t make videos, but here are the slides. Click on talk titles to see abstracts of the talks. For a multi-author talk, the person whose name is in boldface is the one who gave the talk. You also might enjoy comparing the 2017 talks.

Saturday November 9, 2019

8:00 a.m.
Fibrations as generalized lens categoriestalk slides.
David I. Spivak, Massachusetts Institute of Technology

9:00 a.m.
Supplying bells and whistles in symmetric monoidal categoriestalk slides.
Brendan Fong, Massachusetts Institute of Technology
David I. Spivak, Massachusetts Institute of Technology

9:30 a.m.
Right adjoints to operadic restriction functorstalk slides.
Philip Hackney, University of Louisiana at Lafayette
Gabriel C. Drummond-Cole, IBS Center for Geometry and Physics

10:00 a.m.
Duality of relationstalk slides.
Alexander Kurz, Chapman University

10:30 a.m.
A synthetic approach to stochastic maps, conditional independence, and theorems on sufficient statisticstalk slides.
Tobias Fritz, Perimeter Institute for Theoretical Physics

3:00 p.m.
Constructing symmetric monoidal bicategories functoriallytalk slides.
Michael Shulman, University of San Diego
Linde Wester Hansen, University of Oxford

3:30 p.m.
Structured cospanstalk slides.
Kenny Courser, University of California, Riverside
John C. Baez, University of California, Riverside

4:00 p.m.
Generalized Petri netstalk slides.
Jade Master, University of California, Riverside

4:30 p.m.
Formal composition of hybrid systemstalk slides and website.

Paul Gustafson, Wright State University
Jared Culbertson, Air Force Research Laboratory
Dan Koditschek, University of Pennsylvania
Peter Stiller, Texas A&M University

5:00 p.m.
Strings for cartesian bicategoriestalk slides.
M. Andrew Moshier, Chapman University

5:30 p.m.
Defining and programming generic compositions in symmetric monoidal categoriestalk slides.
Dmitry Vagner, Los Angeles, CA

Sunday November 10, 2019

8:00 a.m.
Mathematics for second quantum revolutiontalk slides.
Zhenghan Wang, UCSB and Microsoft Station Q

9:00 a.m.
A compositional and statistical approach to natural languagetalk slides.
Tai-Danae Bradley, CUNY Graduate Center

9:30 a.m.
Exploring invariant structure in neural activity with applied topology and category theorytalk slides.
Brad Theilman, UC San Diego
Krista Perks, UC San Diego
Timothy Q Gentner, UC San Diego

10:00 a.m.
Of monks, lawyers and villages: new insights in social network science — talk cancelled due to illness.
Nina Otter, Mathematics Department, UCLA
Mason A. Porter, Mathematics Department, UCLA

10:30 a.m.
Functorial cluster embeddingtalk slides.

Steve Huntsman, BAE Systems FAST Labs

2:00 p.m.
Quantitative equational logictalk slides.
Prakash Panangaden, School of Computer Science, McGill University
Radu Mardare, Strathclyde University
Gordon D. Plotkin, University of Edinburgh

3:00 p.m.
Brakes: an example of applied category theorytalk slides in PDF and Powerpoint.
Eswaran Subrahmanian, Carnegie Mellon University / National Institute of Standards and Technology

3:30 p.m.
Intuitive robotic programming using string diagramstalk slides.
Blake S. Pollard, National Institute of Standards and Technology

4:00 p.m.
Metrics on functor categoriestalk slides.
Vin de Silva, Department of Mathematics, Pomona College

4:30 p.m.
Hausdorff and Wasserstein metrics on graphs and other structured datatalk slides.
Evan Patterson, Stanford University