## Applied Category Theory 2022

25 February, 2022

The Fifth International Conference on Applied Category Theory, ACT2022, will take place at the University of Strathclyde from 18 to 22 July 2022, preceded by the Adjoint School 2022 from 11 to 15 July. This conference follows previous events at Cambridge (UK), Cambridge (MA), Oxford and Leiden.

Applied category theory is important to a growing community of researchers who study computer science, logic, engineering, physics, biology, chemistry, social sciences, linguistics and other subjects using category-theoretic tools. The background and experience of our members is as varied as the systems being studied. The goal of the Applied Category Theory conference series is to bring researchers together, strengthen the applied category theory community, disseminate the latest results, and facilitate further development of the field.

### Submissions

We accept submissions in English of original research papers, talks about work accepted/submitted/published elsewhere, and demonstrations of relevant software. Accepted original research papers will be published in a proceedings volume. The keynote addresses will be chosen from the accepted papers. The conference will include an industry showcase event and community meeting. We particularly encourage people from underrepresented groups to submit their work and the organizers are committed to non-discrimination, equity, and inclusion.

### Submission formats

Extended Abstracts should be submitted describing the contribution and providing a basis for determining the topics and quality of the anticipated presentation (1-2 pages). These submissions will be adjudicated for inclusion as a talk at the conference. Such work should include references to any longer papers, preprints, or manuscripts providing additional details.

Conference Papers should present original, high-quality work in the style of a computer science conference paper (up to 14 pages, not counting the bibliography; detailed proofs may be included in an appendix for the convenience of the reviewers). Such submissions should not be an abridged version of an existing journal article (see item 1) although pre-submission Arxiv preprints are permitted. These submissions will be adjudicated for both a talk and publication in the conference proceedings.

Software Demonstrations should be submitted in the format of an Extended Abstract (1-2 pages) giving the program committee enough information to assess the content of the demonstration. We are particularly interested in software that makes category theory research easier, or uses category theoretic ideas to improve software in other domains.

Extended abstracts and conference papers should be prepared with LaTeX. For conference papers please use the EPTCS style files available at

http://style.eptcs.org

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

### Important dates

The following dates are all in 2022, and Anywhere On Earth.

• Submission Deadline: Monday 9 May
• Author Notification: Tuesday 7 June
• Camera-ready version due: Tuesday 28 June
• Adjoint School: Monday 11 to Friday 15 July
• Main Conference: Monday 18 to Friday 22 July

### Conference format

We hope to run the conference as a hybrid event with talks recorded or streamed for remote participation. However, due to the state of the pandemic, the possibility of in-person attendance is not yet confirmed. Please be mindful of changing conditions when booking travel or hotel accommodations.

### Program committee

• Jade Master, University of Strathclyde (Co-chair)
• Martha Lewis, University of Bristol (Co-chair)

The full program committee will be announced soon.

### Organizing committee

• Jules Hedges, University of Strathclyde
• Jade Master, University of Strathclyde
• Fredrik Nordvall Forsberg, University of Strathclyde
• James Fairbanks, University of Florida

### Steering committee

• John Baez, University of California, Riverside
• Bob Coecke, Cambridge Quantum
• Dorette Pronk, Dalhousie University
• David Spivak, Topos Institute

## Learning Computer Science With Categories

26 January, 2022

The first book in Bob Coecke’s series on applied category theory is out, and the pdf is free—legally, even!—until 8 February 2022. Grab a copy now:

• Noson Yanofsky, Theoretical Computer Science for the Working Category Theorist, Cambridge U. Press, 2022.

There are already books on category theory for theoretical computer scientists. Why the reverse? Yanofsky explains:

There’s just one catch: you need to know category theory.

But it’s worth learning category theory, because it’s like a magic key to many subjects. It helps you learn more, faster.

## Categories in Chemistry, Computing, and Social Networks

26 January, 2022

• John Baez, Simon Cho, Daniel Cicala, Nina Otter, and Valeria de Paiva, Applied category theory in chemistry, computing, and social networks, Notices of the American Mathematical Society, February 2022.

It urges you — or your friends, or students — to apply for our free summer school in applied category theory run by the American Mathematical Society. It’s also a quick intro to some key ideas in applied category theory!

Applications are due Tuesday 2022 February 15 at 11:59 Eastern Time — go here for details. If you get in, you’ll get an all-expenses-paid trip to a conference center in upstate New York for a week in the summer. There will be a pool, bocci, lakes with canoes, woods to hike around in, campfires at night… and also whiteboards, meeting rooms, and coffee available 24 hours a day.

You can work with me on categories in chemistry, Nina on categories in the study of social networks, or Valeria on categories applied to concepts from computer science, like lenses.

There are also other programs to choose from. Read this, and click for more details:

## Complex Adaptive System Design (Part 10)

25 June, 2021

guest post by John Foley

Though the Complex Adaptive System Composition and Design Environment (CASCADE) program concluded in Fall 2020, just this week two new articles came out reviewing the work and future research directions:

• John Baez and John Foley, Operads for designing systems of systems, Notices of the American Mathematical Society 68 (2021), 1005–1007.

• John Foley, Spencer Breiner, Eswaran Subrahmanian and John Dusel, Operads for complex system design specification, analysis and synthesis, Proceedings of the Royal Society A 477 (2021), 20210099.

#### Operads for Designing Systems of Systems

The first is short and sweet (~2 pages!), aimed at a general mathematical audience. It describes the motivation for CASCADE and how basic modeling issues for point-to-point communications led to the development network operads:

This figure depicts the prototypical example of this style of operad, the ‘simple network operad’, acting on an algebra of graphs whose nodes are endowed with locations and edges can be no longer than a fixed range limit. For more information, check out the article or Part 4 of this series.

For a quick, retrospective overview of CASCADE, this note is hard to beat, so I won’t repeat more here.

#### Operads for complex system design specification, analysis and synthesis

The second article is a full length review, aimed at a general applied science audience:

We introduce operads for design to a general scientific audience by explaining what the operads do relative to broadly applied techniques and how specific domain problems are modelled. Research directions are presented with an eye towards opening up interdisciplinary partnerships and continuing application-driven investigations to build on recent insights.

The review describes how operads apply to system design problems through three examples:

and concludes with a discussion of future research directions. The specification and synthesis examples come from applications of network operads in CASCADE, but the analysis example was contributed by collaborators Spencer Breiner and Eswaran Subrahmanian at the National Institute of Standards and Technology (NIST), who analyzed the Length Scale Interferometer (LSI) at NIST headquarters. Readers interested in a quick introduction to these examples should head directly to Section 3 of the review.

As we describe:

The present article captures an intermediate stage of technical maturity: operad-based design has shown its practicality by lowering barriers of entry for applied practitioners and demonstrating applied examples across many domains. However, it has not realized its full potential as an applied meta-language. Much of this recent progress is not focused solely on the analytic power of operads to separate concerns. Significant progress on explicit specification of domain models and techniques to automatically synthesize designs from basic building blocks has been made.

With this context, CASCADE’s contribution was prototyping general-purpose methods to specify basic building blocks and synthesize composite systems from atoms. By testing these methods against specific domain problems, we learned that domain-specific information should be exploited but systematically fitting together general-purpose and computationally efficient methods is challenging. Moreover, no reconciliation between the analytic point-of-view on operads for system design and the `generative’ perspective of network operads, which facilitate specification and synthesis, has been established. The review does not address how these threads might fit together precisely, but perhaps the answer looks something like this:

For more discussion of future research directions, please see Section 7 of the review, especially the open problems listed in 7f.

For readers that make it through the examples in Sections 4, 5 and 6 of the review but still want more, the following references provide additional details:

• John Baez, John Foley, Joe Moeller and Blake Pollard, Network models, Theory and Applications of Categories 35 (2020), 700–744.

• Spencer Breiner, Olivier Marie-Rose, Blake Pollard and Eswaran Subrahmanian, Modeling hierarchical system with operads, Electron. Proc. Theor. Comput. Sci. 323 (2020) 72–83.

• John Baez, John Foley and Joe Moeller, Network models from Petri nets with catalysts, Compositionality 1 (4) (2017).

Here’s the whole series of posts:

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.

Part 10 – Two papers reviewing the whole project.

## Compositional Robotics (Part 2)

27 May, 2021

Very soon we’re having a workshop on applications of category theory to robotics:

2021 Workshop on Compositional Robotics: Mathematics and Tools, online, Monday 31 May 2021.

You’re invited! As of today it’s not too late to register and watch the talks online, and registration is free. Go here to register:

Here’s the schedule. All times are in UTC, so the show starts at 9:15 am Pacific Time:

Time (UTC) Speaker

Title

16:15-16:30   Intro and plan of the workshop

16:30-17:10

Jonathan Lorand

Category Theory Basics

17:20-18:00

John Baez Category Theory and Systems

Breakout rooms

18:30-19:10

Andrea Censi
& Gioele Zardini

Categories for Co-Design

19:20-20:00

David Spivak

Dynamic Interaction Patterns

Breakout rooms

20:30-21:15

Aaron Ames

A Categorical Perspective on Robotics

21:30-22:15 Daniel Koditschek Toward a Grounded Type Theory for Robot Task Composition
22:30-00:30 Selected speakers Talks from open submissions

For more information go to the workshop website or my previous blog post on this workshop:

## Category Theory and Systems

27 May, 2021

I’m giving a talk on Monday the 31st of May, 2021 at 17:20 UTC, which happens to be 10:20 am Pacific Time for me. You can see my slides here:

I’ll talk about how to describe open systems as morphisms in symmetric monoidal categories, and how to use ‘functorial semantics’ to describe the behavior of open systems.

It’s part of the 2021 Workshop on Compositional Robotics: Mathematics and Tools, and if you click the link you can see how to attend!  If you stick around for the rest of the workshop you’ll hear more concrete talks from people who really work on robotics.

## Compositional Robotics (Part 1)

20 April, 2021

A bunch of us are organizing a workshop on applications of category theory to robotics, as part of the IEEE International Conference on Robotics and Automation:

2021 Workshop on Compositional Robotics: Mathematics and Tools, online, 31 May 2021. Organized by Andrea Censi, Gioele Zardini, Jonathan Lorand, David Spivak, Brendan Fong, Nina Otter, Paolo Perrone, John Baez, Dylan Shell, Jason Kane, Alexandra Nilles, Andew Spielberg, and Emilio Frazzoli.

Submit your papers here by 21 May 2021!

Here’s the idea of the workshop:

In the last decade research on embodied intelligence has seen important developments. While the complexity of robotic systems has dramatically increased, both for single robots and interacting multi-robot systems (e.g., autonomous vehicles and mobility systems), the design methods have not kept up.

The standard answer to dealing with complexity is exploiting compositionality, but there are no well-established mathematical modeling and design tools that have the reach for compositional analysis and design at the level of a complex robotic system.

The goal of this workshop is to integrate mathematical principles and practical tools for compositional robotics, with a focus on applied category theory as a meta-language to talk about compositionality.

The workshop will happen on May 31st virtually. Details will follow.

#### Session I: Mathematics and Tools for Compositionality

In the morning, some of the world’s leading experts in Applied Category Theory (ACT) will provide tutorials to present an invitation to various aspects of compositionality, both at the theoretical and the practical level. In particular, Dr. Jonathan Lorand will teach Category Theory basics, Dr. David Spivak and Dr. Brendan Fong will introduce the audience to the concept of compositionality, Prof. John Baez will explain how the previously defined concepts can be used when modeling various types of systems, and Dr. Andrea Censi will present the theory of co-design, tailored to robotic applications.

#### Session II: Keynote Talks and Open Contributions

The afternoon session features two keynotes on the application of compositionality in robotics:

• Prof. Aaron Ames, Bren Professor of Mechanical and Civil Engineering and Control and Dynamical Systems, California Institute of Technology.

• Prof. Daniel Koditschek, Alfred Fitler Moore Professor of Electrical & Systems Engineering, School of Engineering & Applied Science, University of Pennsylvania. Prof. Koditschek will be assisted by Dr. Paul Gustafson (Wright State University) and Dr. Matthew Kvalheim (University of Pennsylvania).

Both speakers are leading experts in their fields and have succesfully applied category theory and compositionality to real challenges in robotics. Finally, we plan for eight talk-slots for open submissions. Submissions should focus on mathematical perspectives (not limited to ACT) and applications of compositionality.

## Applied Category Theory 2021 — Call for Papers

16 April, 2021

The deadline for submitting papers is coming up soon: May 12th.

Fourth Annual International Conference on Applied Category Theory (ACT 2021), July 12–16, 2021, online and at the Computer Laboratory of the University of Cambridge.

Plans to run ACT 2021 as one of the first physical conferences post-lockdown are progressing well. Consider going to Cambridge! Financial support is available for students and junior researchers.

Applied category theory is a topic of interest for a growing community of researchers, interested in studying many different kinds of systems using category-theoretic tools. These systems are found across computer science, mathematics, and physics, as well as in social science, linguistics, cognition, and neuroscience. The background and experience of our members is as varied as the systems being studied. The goal of the Applied Category Theory conference series is to bring researchers together, disseminate the latest results, and facilitate further development of the field.

We accept submissions of both original research papers, and work accepted/submitted/ published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume. The keynote addresses will be drawn from the best accepted papers. The conference will include an industry showcase event.

We hope to run the conference as a hybrid event, with physical attendees present in Cambridge, and other participants taking part online. However, due to the state of the pandemic, the possibility of in-person attendance is not yet confirmed. Please do not book your travel or hotel accommodation yet.

### Financial support

We are able to offer financial support to PhD students and junior researchers. Full guidance is on the webpage.

### Important dates (all in 2021)

• Submission Deadline: Wednesday 12 May
• Author Notification: Monday 7 June
• Financial Support Application Deadline: Monday 7 June
• Financial Support Notification: Tuesday 8 June
• Priority Physical Registration Opens: Wednesday 9 June
• Ordinary Physical Registration Opens: Monday 13 June
• Reserved Accommodation Booking Deadline: Monday 13 June
• Adjoint School: Monday 5 to Friday 9 July
• Main Conference: Monday 12 to Friday 16 July

### Submissions

The following two types of submissions are accepted:

Proceedings Track. Original contributions of high-quality work consisting of an extended abstract, up to 12 pages, that provides evidence of results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submission of work-in-progress is encouraged, but it 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 that these pages contain sufficient evidence of the quality and rigour of your work.

Papers in the two tracks will be reviewed against the same standards of quality. Since ACT is an interdisciplinary conference, we use two tracks to accommodate the publishing conventions of different disciplines. For example, those from a Computer Science background may prefer the Proceedings Track, while those from a Mathematics, Physics or other background may prefer the Non-Proceedings Track. However, authors from any background are free to choose the track that they prefer, and submissions may be moved from the Proceedings Track to the Non-Proceedings Track at any time at the request of the authors.

Contributions must be submitted in PDF format. Submissions to the Proceedings Track must be prepared with LaTeX, using the EPTCS style files available at http://style.eptcs.org.

The submission link will soon be available on the ACT2021 web page: https://www.cl.cam.ac.uk/events/act2021

### Program Committee

Chair:

• Kohei Kishida, University of Illinois, Urbana-Champaign

Members:

• Richard Blute, University of Ottawa
• Spencer Breiner, NIST
• Daniel Cicala, University of New Haven
• Robin Cockett, University of Calgary
• Bob Coecke, Cambridge Quantum Computing
• Geoffrey Cruttwell, Mount Allison University
• Valeria de Paiva, Samsung Research America and University of Birmingham
• Brendan Fong, Massachusetts Institute of Technology
• Jonas Frey, Carnegie Mellon University
• Tobias Fritz, Perimeter Institute for Theoretical Physics
• Fabrizio Romano Genovese, Statebox
• Helle Hvid Hansen, University of Groningen
• Jules Hedges, University of Strathclyde
• Chris Heunen, University of Edinburgh
• Alex Hoffnung, Bridgewater
• Martti Karvonen, University of Ottawa
• Kohei Kishida, University of Illinois, Urbana -Champaign (chair)
• Martha Lewis, University of Bristol
• Bert Lindenhovius, Johannes Kepler University Linz
• Ben MacAdam, University of Calgary
• Dan Marsden, University of Oxford
• Jade Master, University of California, Riverside
• Joe Moeller, NIST
• Koko Muroya, Kyoto University
• Simona Paoli, University of Leicester
• Daniela Petrisan, Université de Paris, IRIF
• Peter Selinger, Dalhousie University
• Michael Shulman, University of San Diego
• David Spivak, MIT and Topos Institute
• Joshua Tan, University of Oxford
• Dmitry Vagner
• Jamie Vicary, University of Cambridge
• John van de Wetering, Radboud University Nijmegen
• Vladimir Zamdzhiev, Inria, LORIA, Université de Lorraine
• Maaike Zwart

## Language Complexity (Part 7)

23 March, 2021

David A. Tanzer

Higher complexity classes

In Part 6, we saw a program with quadratic complexity. The collection of all languages that can be decided in $O(n^k)$ time for some $k$ is called P, for polynomial time complexity.

Now let’s consider languages that appear to require time that is exponential in the size of the input, and hence lie outside of P.

Here is a decision problem that is believed to be of this sort. Say you are given a description of a boolean circuit, involving AND, OR and NOT gates, which has N inputs and one output. Is there a combination of input values that causes the output to be True?

It appears that any general decision procedure for this problem must resort to some form of searching all the possible input combinations. For N inputs, that’s on the order of $2^N$ combinations to be tried. So the computation takes time that is exponential in the number of inputs.

There is a related decision problem for languages. Consider the language of Boolean formulas like (not(X7) and (X1 or not(X2 and X1)). The query is to find assignments of True/False to each of the variables which satisfy the formula, i.e., which make it evaluate to True.

Note that each Boolean formula is equivalent to a Boolean circuit, and a satisfying assignment to the variables is tantamount to an input combination which causes the circuit to output True.

Let SAT be the language consisting of Boolean formulas which are satisfiable, i.e., for which a satisfying assignment exists. For example, the formula (X1 and X2) belongs to SAT, because it is satisfied by the assignment X1=True, X2=True. On the other hand, (X1 and not(X1)) has no satisfying assignment, and so it does not belong to SAT.

Apparently, a decider for SAT must end up resorting to trying an exponential number of combinations. Now the number of variables in a formula is $O(n)$. A brute force search through input combinations means exponential time complexity.

Could some clever person figure out a better method, which runs in polynomial time? Not if the widely believed conjecture that P != NP holds true.

## Language Complexity (Part 6)

18 March, 2021

David A. Tanzer

In Part 5 we introduced big O notation for describing linear complexity. Now let’s look at a function with greater than linear complexity:

``````def square_length(text):
# compute the square of the length of text
# FIXME: not the most elegant or efficient approach
n = length(text)
counter = 0
for i = 1 to n:
for j = 1 to n:
counter = counter + 1
return counter``````

Here, due to the suboptimal implementation, the number of steps is proportional to the square of the size of the input.

Let $f(n) = MaxSteps(\mathit{square\_length}, n)$.

Then $f(n) = O(n^2)$.

This says that f becomes eventually bounded by some quadratic function. On the other hand, it is not the case that $f(n) = O(n)$, as $f(n)$ will eventually exceed any linear function.

Here is the general definition of big O notation:

Definition.   $f(n) = O(g(n))$ means that for some $r > 0$ and $n_1$, we have that $n > n_1 \implies |f(n)| < r g(n)$.

Any function which is eventually bounded by a linear function must also be eventually bounded by a quadratic function, i.e., linear functions are “smaller than” quadratic functions. So $f(n) = O(n)$ makes a stronger statement than $f(n) = O(n^2)$. Generally, we try to make the strongest statement possible about the complexity of a function.