A canonical algebra of open transition systems

Elena Di Lavore, Alessandro Gianola, Mario Román, Nicoletta Sabadini, Paweł Sobociński

Feedback and state are closely interrelated concepts. Categories with
feedback, originally proposed by Katis, Sabadini and Walters, are a weakening
of the notion of traced monoidal categories, with several pertinent
applications in computer science. The construction of the free such categories
has appeared in several different contexts, and can be considered as state
bootstrapping. We show that a categorical algebra for open transition systems,
$\mathbf{Span}(\mathbf{Graph})_\ast$, also due to Katis, Sabadini and Walters,
is the free category with feedback over $\mathbf{Span}(\mathbf{Set})$.
Intuitively, this algebra of transition systems is obtained by adding state
to an algebra of predicates, and therefore $\mathbf{Span}(\mathbf{Graph})_\ast$
is, in this sense, the canonical such algebra.