Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: An Algebraic Theory of Systems

Suraaj K S (Aug 28 2024 at 14:26):

My question has to do with defining a notion of an "Algebra of Open Systems", similar to how we have Group theory for symmetries.

Informally, a system should have a set (usually finite?) of interfaces, and we should be able to compose systems in parallel and sequentially. One paper which seems to do this is: https://www.sciencedirect.com/science/article/pii/S0304397518304092. An overview of their system algebra is, informally, as follows:

We have:

A set of systems
A (partial) parallel composition binary operation - What system do you get when you have two systems in parallel
An interface connection operation - Given a system, what system do you get if you connect two of its interfaces

Moreover, they need to satisfy some axioms (given in the paper). (PS: IMO, these are the main ideas. In order to define these, you need other auxillary functions. For example, you need a function mapping a system to its set of interfaces).

However, CT already seems to give us a notion of an algebraic theory of systems - Symmetric Monoidal Categories.
What I am curious about is - what extra structure to we need to impose on SMCs to make them 'almost equivalent' to the ideas in the paper? For instance,

In the paper, there is an interface connection operation, which just connects two interfaces of a system. In fact, sequential composition is defined in terms of this operation.
In the paper, an interface is 'reactive', and do both inputs and outputs. What extra structure do we need to impose on SMCs to model this?

Spencer Breiner (Aug 28 2024 at 14:58):

I haven't read the paper, so take this reply with a grain of salt :sweat_smile:

1) First, I would usually prefer to say that SMCs are theory of processes, rather than of systems, because they are inherently directed. For some extensions to get around this you could look at [[compact closed category]], [[dagger-compact category]] and [[hypergraph category]].

2) These will often be categories of [[span]] or [[relation]] (sic, plurals break links), in which case we usually think of a morphism as some kind of joint constraint over inputs and outputs. In particular, this doesn't directly address the bi-directionality of sequential interfaces, though it doesn't forbid it either.

3) There is by now a fairly large literature on CT for bidirectional processes. Some relevant topics here are [[lens (in computer science) ]], [[optic (in computer science)]] and [[polynomial functor]]. Very roughly,

lenses are getters and setters with fixed (Cartesian) types
(morphisms between) polynomial functors are getters and setters with variable (Cartesian) types (possible inputs depend on current states/outputs)
optics are getters and setters in more general monoidal settings.

4) From an SMC perspective, it is strange that parallel composition is a partial operation. Do the authors provide intuitions about when this is expected to fail? One possible example that comes to mind is systems located in space(time), where we might not be able to parallel-compose two different systems located at the same place.

Suraaj K S (Aug 28 2024 at 15:20):

Spencer Breiner said:

From an SMC perspective, it is strange that parallel composition is a partial operation. Do the authors provide intuitions about when this is expected to fail?

I think that parallel composition is only defined if the interfaces of the two systems are disjoint

Spencer Breiner (Aug 28 2024 at 15:23):

That makes sense. This is already enforced by $\otimes$ , since $f\otimes g: X\otimes Y\to X'\otimes Y'$ .

Spencer Breiner (Aug 28 2024 at 15:24):

I.e., the inputs/outputs of $f$ and $g$ are automatically disjoint.

Suraaj K S (Aug 28 2024 at 15:47):

What I think I'd really want is a CT variant of that paper - where we could model distributed systems, etc. I don't know if lenses, etc. do that

Spencer Breiner (Aug 28 2024 at 15:58):

One other topic that I intended to mention is [[duoidal category]]. There are a couple of recent papers by Earnshaw, et al and Shapiro & Spivak in this direction.

Spencer Breiner (Aug 28 2024 at 16:04):

Suraaj K S said:

What I think I'd really want is a CT variant of that paper - where we could model distributed systems, etc. I don't know if lenses, etc. do that

The basic idea is that a [[Moore machine]] with state set $S$ , inputs $I$ and outputs $)$ can be viewed as a lens mapping $\begin{pmatrix}S\\S\end{pmatrix}\leftrightarrows\begin{pmatrix}I\\O\end{pmatrix}$ . You can think of these as stream transducers, which can compose via wiring diagrams to form "larger" transducers.

I'm not sure if that will meet your needs or not. Do you have a toy example to play with?

Spencer Breiner (Aug 28 2024 at 16:07):

Some other good (if lengthy) places to look are the books by Niu & Spivak or Myers.

Suraaj K S (Aug 28 2024 at 16:13):

@_**Spencer Breiner|278008** [said]
I'm not sure if that will meet your needs or not. Do you have a toy example to play with?

I think https://en.wikipedia.org/wiki/Kahn_process_networks

(which are also mentioned in the paper) are a good toy example

Suraaj K S (Aug 28 2024 at 16:15):

Kahn Networks are a little limited though. There are systems which cannot be modeled as KPNs..

For instance, a system with 2 input interfaces, and one output interface, which "merges" messages (whichever come first in time) cannot be modelled via a Kahn Network

Owen Lynch (Aug 28 2024 at 21:29):

I think that the philosophy given by David Jaz's book on systems theory might fit the bill here: http://davidjaz.com/Papers/DynamicalBook.pdf.