🔢 mathematics

Finite Observations, Infinite Behaviour: bicategorical semantics for stateful monoidal processes

This paper introduces a bicategorical semantics for stateful monoidal processes that equates systems based on their finite observational constraints rather than internal states, providing a functorial framework for feedback categories and establishing a categorified compactness theorem that unifies diverse process types, including non-deterministic and linear time-invariant systems.

Original authors: Cole Comfort, Giovanni de Felice

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Cole Comfort, Giovanni de Felice

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a mysterious machine. You can't see inside it; you can't see its gears, its memory chips, or its internal code. All you can do is watch what goes in and what comes out.

This paper is about how to define when two of these mysterious machines are actually doing the exact same thing, even if they are built completely differently on the inside.

Here is the breakdown of their ideas using simple analogies:

1. The Problem: The "Black Box" Mystery

Most systems in the world (like a radio, a stock market algorithm, or a quantum computer) have an internal state. Think of this state as a hidden diary.

The Old Way: To say two machines are the same, mathematicians usually tried to simulate the machine running forever. They would say, "If Machine A and Machine B produce the exact same infinite stream of outputs for every possible input, they are equal."
The Problem: This breaks down when the machines are messy. If a machine is partial (it might crash), nondeterministic (it might flip a coin to decide), probabilistic (it works 90% of the time), or quantum (it exists in multiple states at once), you can't always predict the "infinite future." The simulation might get stuck or become impossible to calculate.

2. The Solution: The "Finite Detective" Approach

Instead of trying to predict the infinite future, the authors propose a new rule: We only care about what we can actually observe in finite time.

Imagine you are a detective interviewing two suspects (the machines). You can't see their minds, but you can ask them questions (inputs) and listen to their answers (outputs).

The Rule: Two machines are considered "the same" if, for every finite test you can run on Machine A, Machine B can pass that same test (perhaps with a little more context), and vice versa.
The Analogy: It's like two people claiming to be the same person. You don't need to know their entire life story to verify this. You just need to check that every fact you know about Person A is also true for Person B. If Person A says, "I was in Paris in 2020," and Person B can also confirm they were in Paris in 2020, that's a match. If Person A says, "I can fly," and Person B cannot, they are different.

3. The "Discard" Concept: Forgetting is Useful

The paper introduces a mathematical structure called a "Discard Bicategory."

The Metaphor: Imagine a conversation where you can choose to ignore part of the information. If I tell you a long story, and you only care about the ending, you "discard" the middle.
Why it matters: In the real world, we often don't care about every single detail of a system. We might not care about the internal memory of a computer, only the final result. This math allows the authors to formally "throw away" the internal state and focus purely on the relationship between inputs and outputs.

4. The "Compactness" Theorem: The Puzzle Piece Magic

One of the paper's coolest results is a "Compactness Theorem."

The Analogy: Imagine you have a giant, infinite jigsaw puzzle. You can't see the whole picture at once. However, you have a rule: if you can fit together any finite collection of puzzle pieces without them clashing, then there must be a way to assemble the entire infinite puzzle perfectly.
The Result: The authors prove that if you have a consistent set of finite observations (puzzle pieces) for a system, you can mathematically glue them together to form a single, perfect, infinite description of that system's behavior. This works specifically for systems that behave like "closed relations" (like sets of possible outcomes).

5. Real-World Examples They Cover

The authors show this math works for many different types of "machines":

Deterministic: Standard computers (like a calculator).
Nondeterministic: Machines that make random choices (like a dice-rolling robot).
Probabilistic: Machines that deal with probabilities (like weather forecasting models).
Quantum: Machines that use quantum physics (where things can be in two states at once).

6. The "Time" Aspect

The paper also handles time beautifully.

The Metaphor: Imagine a movie reel. Usually, you watch it from start to finish. But this math allows you to look at a scene, then look at the next scene, and realize that the "delay" between them doesn't change the story.
The Result: They prove that if you shift the time of your observations (watch the movie 5 minutes later), the fundamental "behavior" of the machine remains the same. This allows them to treat systems that run forever (like a signal flow graph) as a single, unified object.

Summary

In short, this paper provides a new mathematical language to describe complex, stateful machines. Instead of getting bogged down by trying to simulate their infinite internal lives, it says: "If two machines pass the same finite tests, they are the same."

This approach is robust enough to handle messy, random, and quantum systems, and it proves that if you have enough consistent local observations, you can reconstruct the entire infinite behavior of the system. It's a way of defining "identity" for machines based on what we can actually see, rather than what we can't.

Technical Summary: Finite Observations, Infinite Behaviour

Problem Statement

Time-dependent systems, such as signal flow graphs, stochastic processes, and quantum channels with memory, are often modeled as stateful processes (e.g., Mealy machines) that maintain internal memory. While the behavior of deterministic systems is well-understood via coinductive fixed points, this characterization breaks down when processes are partial, non-deterministic, probabilistic, or quantum. In these settings, the coinductive fixed point may not exist, and standard definitions of behavioral equivalence fail.

The central question motivating this work is: When do two stateful processes produce the same infinite behavior? The authors seek a denotational answer that relies solely on finite, local observations rather than a priori global constraints. The challenge is to define a semantic construction where two processes are equivalent if they impose the same constraints on their inputs and outputs, as determined by finite observations, independent of their internal state.

Methodology

1. Structural Foundation: Discard Bicategories

The authors introduce a structural framework called a discard bicategory. This is a preorder-enriched symmetric monoidal category equipped with a "discard" morphism ( $\top_X: X \to I$ ) for every object, representing the ability to ignore information.

Preorder Enrichment: Hom-sets are equipped with a preorder ( $\subseteq$ ) allowing the comparison of processes by their informativeness (approximation).
Lax Naturality of Discard: The discard operation is compatible with approximation ( $\top_Y \circ f \subseteq \top_X$ ), meaning running a process and then discarding is less informative than discarding the input directly.
Scope: This structure unifies various process theories, including partial functions (restriction order), relations (subset inclusion), probabilistic kernels (conditional order), and quantum channels (purification order).

2. Semantic Construction: The Category of Behaviors

The core contribution is the construction of a discard bicategory of behaviors, denoted $\text{Obs}_{I,J}(\mathcal{C})$ .

Contexts: The construction is parametrized by an index set $I$ (representing time or space) and a collection $J$ of finite subsets of $I$ (contexts).
Monotone Families: A behavior is defined as a "monotone family" of observations. This is a family of morphisms $\{f_j\}_{j \in J}$ , where each $f_j$ describes the process restricted to a finite context $j$ .
Consistency Condition: The family must be consistent: observations in a larger context $j'$ must refine those in a smaller context $j$ (formally, $(1 \otimes \top) \circ f_{j'} \subseteq f_j \otimes \top$ ).
Observational Equivalence: Two processes are identified if they are observationally equivalent: every observation of one can be verified by an observation of the other, possibly in a larger context. This is formalized as mutual approximation ( $f \subseteq g$ and $g \subseteq f$ ).
Quotienting: The category of behaviors is obtained by quotienting the category of monotone nets by this observational equivalence relation.

3. Integration with Stateful Processes

The authors demonstrate that this construction provides a functorial semantics for stateful processes:

State Reparametrization: The construction identifies stateful processes that differ only by a dinatural reparametrization of their internal state.
Time Delay: The time-delay operation is shown to be a natural transformation. In compact-closed settings, it becomes a natural isomorphism, allowing the construction to form a feedback category in the sense of Katis, Sabadini, and Walters.
Inconsistency Propagation: Unlike previous stream semantics (e.g., coalgebraic streams or extensional streams), this construction propagates inconsistency globally. If a process is inconsistent in any single finite context, its entire behavior is the zero morphism.

Key Results

1. Uniformity and Functoriality

The construction applies uniformly to partial, non-deterministic, probabilistic, and quantum processes. It is functorial with respect to base change, meaning a morphism between underlying process theories induces a morphism between their respective categories of behaviors.

2. The Categorified Compactness Theorem

Focusing on the non-deterministic setting (relations), the authors prove a categorified compactness theorem (Theorem 5.5).

Statement: For the category of closed relations between compact Hausdorff spaces, every compatible family of finite observations (a monotone net) extends uniquely and functorially to a single infinite closed relation.
Significance: This establishes that local consistency implies global existence and uniqueness in this specific setting, effectively "gluing" finite observations into a global behavior.

3. Recovery of Willems' Behaviors

When restricted to affine relations over finite fields, the compactness theorem recovers Willems' notion of behavior for linear time-invariant (LTI) systems.

The authors show that their time-domain semantics for uninitialised LTI systems precisely captures the behaviors defined by Willems as the kernel of a system of constant-coefficient difference equations.
This provides a compositional time-domain semantics for signal flow graphs that was previously elusive in categorical treatments, which had largely relied on frequency-domain (z-domain) interpretations.

4. Comparison with Existing Semantics

The paper argues that existing approaches (stateful morphism sequences, coalgebraic streams, causal sequences) fail to satisfy all desirable properties simultaneously:

Stateful morphism sequences are purely local and fail to propagate inconsistency infinitely.
Coalgebraic streams collapse in the presence of partiality or zero morphisms (becoming indiscrete).
Causal/monotone sequences do not identify dinaturally equivalent streams.
The proposed construction resolves these issues by prioritizing the consistency of finite observations.

Significance and Claims

The paper claims to provide a process-theoretic solution to the problem of defining infinite behavior for stateful systems without relying on coinductive fixed points that may not exist. By shifting the focus from internal state to finite constraints, the authors offer a robust semantic framework that:

Generalizes behavioral equivalence across diverse process theories (deterministic, partial, probabilistic, quantum).
Unifies local and global views of behavior, proving that under specific topological conditions (compact Hausdorff spaces), local observations uniquely determine global behavior.
Reconciles categorical semantics with classical systems theory, specifically recovering Willems' behavioral approach for LTI systems over finite fields within a compositional, time-domain framework.

The authors position their work as a foundational step, noting that while they have established the existence of these behaviors and their properties, the completeness of graphical languages for these behaviors (axiomatization) remains an open problem for future work. They also suggest that generalizing the compactness theorem to probabilistic and quantum settings is a natural next step.