UC Riverside

This thesis aims to develop a compositional theory for the operational semantics of networks. The networks considered are described by either internal or enriched graphs. In the internal case we focus on $\mathsf{Q}$-nets, a generalization of Petri nets based on a Lawvere theory $\mathsf{Q}$. $\mathsf{Q}$-nets include many known variants of Petri nets including pre-nets, integer nets, elementary net systems, and bounded nets. In the enriched case we focus on graphs enriched in a quantale $R$ regarded as matrices with entries in $R$. These $R$-matrices represent distance networks, Markov processes, capacity networks, non-deterministic finite automata, simple graphs, and more. The operational semantics of $\mathsf{Q}$-nets is constructed as an adjunction between $\mathsf{Q}$-nets and categories internal to the category of models of $\mathsf{Q}$. The left adjoint of this adjunction sends a $\mathsf{Q}$-net $P$ to an internal category $F_{\mathsf{Q}}(P)$ whose morphisms represent all possible firing sequences in $P$. Similarly, the operational semantics of $R$-matrices is constructed as an adjunction between $R$-matrices and categories enriched in $R$. The left adjoint of this adjunction sends an $R$-matrix $M$ to the $R$-category $F_R(M)$ whose hom-objects are solutions of the algebraic path problem: a generalization of the shortest path problem to graphs weighted in $R$. For both $\mathsf{Q}$-nets and $R$-matrices we use the theory of structured cospans to study the compositionality of the above operational semantics. For each type of network we construct a double category whose morphisms are ``open networks", i.e.\ networks with certain vertices designated as input or output. The operational semantics gives a double functor from a double category of open networks to a double category of open enriched or internal categories. These double functors give a compositional framework for computing the operational semantics of $\mathsf{Q}$-nets and $R$-matrices: their functoriality and coherence give relationships between the operational semantics of a network and the operational semantics of the smaller networks from which it is composed. We introduce the black-boxing of an open network, a profunctor describing the externally observable behavior of an open network. We introduce a class of open networks called ``functional open networks" for which black-boxing preserves composition.