Temporal semantics for string diagrams

Question

Suppose I have a string diagram $D$ which involves a set of strings $S$ and atomic processes $A$. Formally, we should think of this as a canonically chosen map in the free symmetric monoidal category (SMC) $Free(D)$ generated by objects $S$ and arrows $A\rightrightarrows List(S)$.

Now suppose that I assign a duration to each atomic process $d:A\to\mathbb{R}^+$. I would like to extend this to all the maps in $Free(D)$ and, ideally, this assignment would define a functor on $Free(D)$.

Intuitively, the extension (also denoted $d$) would be defined by $d(f\circ g)=d(f)+d(g)$ and $d(f\otimes g)=max(d(f),d(g))$.

A problem arises for diagrams like this:

---(f)---(g)---

---(h)---(k)---

On one hand, the SMC laws tell us that $$(g\circ f)\otimes (k\circ h)=(g\otimes k)\circ(f\otimes h),$$ but in general we only know that $$\max(d(f)+d(g),d(k)+d(h)) \leq \max(d(f),d(h))+\max(d(g),d(k)).$$

Of course, the assignment of durations to diagrams is not difficult to describe algorithmically: for each path through the diagram, sum up the durations along that path, and take the maximum over those sums (though there are certainly better algorithms).

Ultimately, I am less interested in how to calculate the duration of a diagram, and more interested in whether/how we can express that assignment functorially?

Answer 1

As you correctly note, the overall duration alone is not compositional data on your processes/diagrams. However, the algorithm you describe gives a clue as to how one could obtain duration data on processes which IS compositional, given the same data on the atomic processes.

Instead of keeping track of the overall duration of a process, you can keep track of the minimum duration from any input of the process to any output of the process. When two processes compose (in sequence or in parallel) you can then use the data for each process to compute data for the composite process, as sketched in your algorithm. For atomic processes, you can set the minimum time to be the same number from any input to any output (or you can use a more sophisticated assignment, if you wish). The overall duration for a process is obtained (non-compositionally) by taking the maximum of the minimum times between any input and any output.

To make it formal, let $(R, \max, -\infty, +, 0)$ be any semiring (e.g. the max-plus semiring $\mathbb{R}^+ \sqcup\{-\infty\}$) and consider the symmetric monoidal category $\text{Mat}(R)$ of $R$-valued matrices, with matrix multiplication as composition and direct sum as monoidal product. The duration data described above for a process is easily encoded in a matrix $M$: columns indexed by inputs, rows indexed by outputs, element $M_{i, j}$ encoding the "minimum duration" from the $i$-th input to the $j$-th output. The overall process duration is then the maximum $\max_{i,j}M_{i,j}$ of the matrix elements.

Any assignment of $R$-valued matrices to the atomic processes automatically extends to a monoidal functor, by sending sequential composition of processes to the multiplication of the corresponding matrices and parallel composition of processes to the direct sum of the corresponding matrices. The only thing to check is that the matrices thus associated to sequential and parallel compositions actually encode the data described informally above.

If two processes with matrices $M$ and $N$ are composed in sequence, the matrix for the sequential composition is the matrix product $NM$, encoding the following minimum process duration from input $k$ to output $i$: $$ (NM)_{ik} = \max_j\left(N_{ij}+M_{jk}\right) $$ This is the maximum over all paths from input $k$ to output $i$, as expected.

If two processes with matrices $M$ and $N$ are composed in parallel, the matrix for the parallel composition is the matrix direct sum $M \oplus N$, encoding the following minimum process duration from input $k$ to output $i$:

• if $k$ and $i$ are an input and an output of the first process, $(M \oplus N) = M_{ik}$;
• if $k$ and $i$ are an input and an output of the second process, $(M \oplus N) = N_{ik}$;
• otherwise, $(M \oplus N) = -\infty$.

This is also as expected: the $-\infty$ indicates that there are no paths between inputs of one process and outputs of the other, and hence there are no minimum duration requirements from one to the other.