We present a unified framework for Petri nets and various variants, such as pre-nets and Kock's whole-grain Petri nets. Our framework is based on a less well-studied notion that we call Σ-nets, which allow fine-grained control over whether each transition behaves according to the collective or individual token philosophy. We describe three forms of execution semantics in which pre-nets generate strict monoidal categories, Σ-nets (including whole-grain Petri nets) generate symmetric strict monoidal categories, and Petri nets generate commutative monoidal categories, all by left adjoint functors. We also construct adjunctions relating these categories of nets to each other, in particular showing that all kinds of net can be embedded in the unifying category of Σ-nets, in a way that commutes coherently with their execution semantics.

Abstract The reachability semantics for Petri nets can be studied using open Petri nets. For us, an “open” Petri net is one with certain places designated as inputs and outputs via a cospan of sets. We can compose open Petri nets by gluing the outputs of one to the inputs of another. Open Petri nets can be treated as morphisms of a category Open(Petri), which becomes symmetric monoidal under disjoint union. However, since the composite of open Petri nets is defined only up to isomorphism, it is better to treat them as morphisms of a symmetric monoidal double category ${\mathbb O}$ pen(Petri). We describe two forms of semantics for open Petri nets using symmetric monoidal double functors out of ${\mathbb O}$ pen(Petri). The first, an operational semantics, gives for each open Petri net a category whose morphisms are the processes that this net can carry out. This is done in a compositional way, so that these categories can be computed on smaller subnets and then glued together. The second, a reachability semantics, simply says which markings of the outputs can be reached from a given marking of the inputs.

Algorithmic entropy can be viewed as a special case of the entropy studied in statistical mechanics. This viewpoint allows us to apply many techniques developed for use in thermodynamics to the subject of algorithmic information theory. In particular, suppose we fix a universal prefix-free Turing machine and letXbe the set of programs that halt for this machine. Then we can regardXas a set of ‘microstates’, and treat any function onXas an ‘observable’. For any collection of observables, we can study the Gibbs ensemble that maximises entropy subject to constraints on the expected values of these observables. We illustrate this by taking the log runtime, length and output of a program as observables analogous to the energyE, volumeVand number of moleculesNin a container of gas. The conjugate variables of these observables allow us to define quantities we call the ‘algorithmic temperature’T, ‘algorithmic pressure’Pand ‘algorithmic potential’ μ, since they are analogous to the temperature, pressure and chemical potential. We derive an analogue of the fundamental thermodynamic relationdE=TdS−PdV+μdN, and use it to study thermodynamic cycles analogous to those for heat engines. We also investigate the values ofT,Pand μ for which the partition function converges. At some points on the boundary of this domain of convergence, the partition function becomes uncomputable – indeed, at these points the partition function itself has non-trivial algorithmic entropy.

In physics, Feynman diagrams are used to reason about quantum processes. Similar diagrams can also be used to reason about logic, where they represent proofs, and computation, where they represent programs. With the rise of topological quantum field theory and quantum computation, it became clear that diagrammatic reasoning takes advantage of an extensive network of interlocking analogies between physics, topology, logic and computation. These analogies can be made precise using the formalism of symmetric monoidal closed categories. But symmetric monoidal categories are just the n=l,fc=3 entry of a hypothesized "periodic table" of fc-tuply monoidal n- categories. This raises the question of how these analogies extend. An important clue comes from the way symmetric monoidal closed 2-categories describe rewrite rules in the lambda calculus and multiplicative intuitionistic linear logic. This talk is based on work in progress with Paul-Andre Mellies and Mike Stay.