Nondeterministic behaviours in double categorical systems theory

Research
1

The draft of my paper on nondeterministic behaviours is on the ArXiv: [2502.02517] Nondeterministic Behaviours in Double Categorical Systems Theory

Abstract: In this paper, we build a double theory capturing the idea of nondeterministic behaviours and trajectories. Following Jaz Myers’ Double Categorical Systems Theory, we construct a monoidal double category of systems and interfaces, which then yields (co)representable behaviours. We use conditional products in Markov categories to get compositional trajectories and behaviours, and represent nondeterministic systems and lenses using parametric deterministic maps. The resulting theory can also represent imprecise probability via naming Knightian choices, \emph{à la} Liell-Cock and Staton.

It probably needs some polishing; any feedback is welcome!

The basic ideas are:

  • Use Markov categories with conditionals to handle nondeterminism.
  • In particular, use conditional products to define joint distributions for composite systems.
  • Deal with time using Directed Acyclic Graphs. A state space is, roughly, a contravariant functor whose source is a DAG. For instance, it could be given by objects S(n) encoding trajectories on the (possibly discrete) time interval (0, n), with restriction/clipping maps S(n+1) \rightarrow S(n), for all positive integers n. Same for input and output spaces of interfaces.
  • Handle nondeterministic updates manually, by having systems be deterministic systems with “named sources of nondeterminism”, typically update: S \times I \times \Omega_S \rightarrow S, where \Omega_S is specific to the system S, and is meant to have a nondeterministic behaviour eventually. Thus, for composite systems, one would get \Omega s that are (finite) products of the \Omega s of the component subsystems.

Key questions that remain: Is there a way of dealing with time in a “higher-order” way, e.g. in cartesian closed settings? Does the Markov category of Quasi-Borel spaces ([1701.02547] A Convenient Category for Higher-Order Probability Theory) have conditionals?

1 Like
2

Maybe it is worth emphasizing: in this work, I do not follow the mainstream convention in probability theory, that is “fix a global probabilistic universe \Omega where all the randomness comes from”. On the contrary, I try to systematically keep track of the (nondeterministic) information I use, focusing on the laws of the random variables. As mentioned in the second bullet point above, conditional products enable me to create joint laws for random variables in some contexts.

My motivation comes from the following informal idea: if you want fully compositional modelling, if you’re interested in being able to “glue models together”, etc., it seems like a bad idea to pretend that each of the models has a fixed “universal” source of randomness \Omega, and to have to reconcile those each time you combine models. I am not saying it is impossible, but rather that it seems like one would simply be sweeping the (difficult?) questions regarding joint distributions under this “merging \Omega s operation” rug.

I would be very interested in hearing counterarguments/justifications that other people might have.

3

Update and disclaimer: I realized that the technical conditions for what I call “yz-squares” in the triple categories Arena_{\mathcal{C}} and ArenaSys_{\mathcal{C}} that I define in this draft are too restrictive, and do not capture exactly what I want.
I am working on fixing that; I might also have to change how I define the “double category ArenaSys_{\mathcal{C}}^{\mathcal{G}} of systems and interfaces” in the end.