🔢 mathematics

Between Markov and restriction. Two more monads on categories for relations

This paper extends the existing taxonomy of "categories for relations" by introducing two new, more abstract gs-monoidal categories characterized by axiomatic mass and domain notions, and demonstrates that mass and domain preserving monads naturally generate these categories as Kleisli categories for semiring-weighted relations.

Original authors: Cipriano Junior Cioffo, Fabio Gadducci, Davide Trotta

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Cipriano Junior Cioffo, Fabio Gadducci, Davide Trotta

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 organize a massive library of different types of "relationships" between things. In mathematics and computer science, these relationships are modeled using structures called categories. Some of these categories describe things that are certain and complete (like a perfect map), while others describe things that are partial, probabilistic, or messy (like a sketchy map or a guess).

This paper, titled "Between Markov and restriction," is like a librarian who has just discovered two new, very specific shelves to place these relationship books on. These new shelves sit right in the middle of two existing, well-known sections: the Markov section (dealing with probability and chance) and the Restriction section (dealing with partial or incomplete information).

Here is a breakdown of the paper's main ideas using simple analogies:

1. The Big Picture: The "Relationship" Library

Think of a Symmetric Monoidal Category as a giant warehouse where you can combine things (like mixing ingredients) and duplicate them (like photocopying a document).

Markov Categories are like a warehouse where every item you take out is guaranteed to be "whole" and "complete." Nothing is missing. This is great for probability.
Cartesian Restriction Categories are like a warehouse where items might be "broken" or "incomplete." You can have a function that works only on some inputs, not all. This is great for partial functions.

The authors previously created a map (a taxonomy) showing how these different warehouses relate. In this new paper, they found that there are actually two new types of warehouses that sit right between the "Perfect" and the "Broken" ones.

2. The Two New Concepts: "Mass" and "Domain"

The authors introduce two new ways to measure an arrow (a relationship or a process) in these categories.

Mass (The "Weight" of the Arrow):
Imagine you are shipping a package. The Mass of an arrow is like checking the total weight of the package as it leaves the warehouse.
- In a Mass Category, the rule is: "If you check the weight of the package after it goes through the process, it's the same as checking the weight before it goes through, provided you ignore the destination details."
- It's a way of saying the process doesn't magically create or destroy "stuff" (probability mass) in a specific, abstract way.
Domain (The "Valid Area" of the Arrow):
Imagine a stamp that only works on certain parts of a paper. The Domain is the specific area where the stamp actually leaves a mark.
- In a Domain Category, the rule is: "If you look at the area where the stamp works, and then run the stamp through the process, you get the exact same result as just running the stamp."
- This is a generalization of the idea of "partial functions." It ensures that if a process is defined for a specific input, it behaves consistently.

3. The Discovery: A New Middle Ground

The authors realized that you don't need to be fully "Markov" (perfectly total) or fully "Restriction" (fully partial) to have a useful system.

You can have a system that respects Mass but isn't necessarily fully Markov.
You can have a system that respects Domain but isn't necessarily fully Restriction.

They proved that the famous Markov Categories are actually just the intersection of these two new types: a category is Markov if and only if it is both a Mass category and a "Weakly Markov" category (a specific type of mass category). It's like saying a "Perfect Square" is just a shape that is both a "Perfect Rectangle" and a "Perfect Rhombus."

4. The "Lift" Mechanism: Kleisli Categories

In computer science, there is a tool called a Monad (think of it as a machine that wraps data in a special container, like a box). When you take a category and apply a Monad to it, you get a new category called a Kleisli Category.

The paper asks: If I start with a "Domain" or "Mass" category, and I put it through this machine, does the new category keep those properties?

The Answer: Yes, but only if the machine (the Monad) is built correctly.
They defined "Domain-preserving" and "Mass-preserving" machines. If the machine is built to respect the "Domain" or "Mass" rules, the new category coming out the other side will also respect those rules.
This is a big deal because it allows researchers to build complex probabilistic or partial systems while knowing exactly which rules (axioms) will still hold true.

5. Real-World Examples (The Case Studies)

To prove their theory works, the authors looked at two concrete examples:

Semiring-Weighted Relations: Imagine a system where relationships aren't just "yes/no" (like a standard map) but have "weights" (like a map where roads have traffic scores). They showed that if the math behind these weights (called a "semiring") has certain properties (like being "idempotent," where $x + x = x$ ), then the resulting system automatically becomes a Domain Category. This explains why certain fuzzy logic or probability systems behave the way they do.
Partial Markov Categories: They looked at a system called Partial(FinStoch), which deals with probability distributions that might not exist (partiality). They used their new "Domain-preserving" tools to prove that this system is indeed a Domain Category, offering a fresh, simpler proof of a fact that was previously harder to show.

Summary

In simple terms, this paper is about refining the map of mathematical logic.

The authors found two new "neighborhoods" (Mass and Domain categories) that sit between the neighborhoods of "Probability" and "Partiality."
They showed how to build machines (Monads) that can move data between these neighborhoods without breaking the rules of the neighborhood.
They proved that the famous "Markov" neighborhood is actually just the overlap of these two new neighborhoods.

This helps computer scientists and mathematicians better understand the structural rules that govern how we model uncertainty, partial information, and relationships in code and logic.

Problem Statement
The study of categories abstracting the structural properties of relations has yielded a diverse body of work, including Markov categories (for probabilistic reasoning) and cartesian restriction categories (for partiality). Previous work by the authors established a taxonomy of these categories as instances of gs-monoidal (garbage/share-monoidal) categories, viewing them as Kleisli categories of suitable symmetric monoidal monads. However, a gap remained in the understanding of Kleisli categories generated by specific monads on these bases. Specifically, the authors discovered serendipitously that the Kleisli category of an affine monad on a cartesian restriction category is not necessarily a cartesian restriction category, yet it satisfies a key axiom known as the domain equation. This observation suggested the existence of intermediate structures between gs-monoidal, Markov, and cartesian restriction categories that had not been formally isolated or characterized in the existing taxonomy.

Methodology
The paper employs the framework of symmetric monoidal categories and string diagram calculus to define and analyze new categorical structures. The methodology proceeds through the following steps:

Definition of New Structures: The authors introduce two new classes of categories: mass categories and domain categories. These are defined by axiomatic notions of "mass" (an arrow to the monoidal unit) and "domain" (an arrow from an object to itself), generalizing concepts from restriction categories and weakly Markov categories.
Functorial Analysis: The paper investigates functors that preserve these structures. It generalizes the concepts of affine and relevant functors to define mass-preserving and domain-preserving functors.
Kleisli Category Lifting: The core technical work involves proving conditions under which the Kleisli category of a symmetric monoidal monad inherits the mass or domain structure of its base category. This relies on detailed diagrammatic calculations involving the monad's structural arrows (multiplication, unit, and coherence maps).
Decomposition and Characterization: The authors use these results to decompose known categories (specifically Markov categories) into combinations of the newly defined structures.
Case Studies: The theory is instantiated in two specific contexts:
- Semiring-weighted relations: Analyzing the semiring monad to determine when it yields domain or mass categories based on algebraic properties of the underlying semiring (e.g., idempotence and absorption).
- Partial Markov categories: Re-characterizing the category Partial(FinStoch) as a Kleisli category of a lifted monad, proving it is a domain category.

Key Contributions

New Categorical Taxonomy: The paper introduces mass categories and domain categories as intermediate structures between gs-monoidal and cartesian restriction categories.
- A domain category satisfies the domain equation: $dom(f); f = f$.
- A mass category satisfies the mass equation: $dom(f); mass(f) = mass(f)$.
Decomposition of Markov Categories: A significant theoretical result is the proof that a category is a Markov category if and only if it is both a mass category and a weakly Markov category. This provides a finer algebraic characterization of Markov categories in terms of idempotent and group structures on hom-sets.
Kleisli Lifting Theorems: The authors establish precise conditions for when Kleisli categories preserve these structures:
- A symmetric monoidal monad $T$ on a cartesian restriction category is domain preserving if and only if its Kleisli category is a domain category.
- $T$ is mass preserving (or unital domain preserving) if and only if its Kleisli category is a mass category.
Functorial Characterizations: The paper links these new categories to functor properties, showing that affine functors are domain preserving, and providing a decomposition of affine functors into weakly affine and unital domain preserving components.
Algebraic Instantiations:
- It is shown that the semiring monad yields a domain category if the semiring is absorptive and idempotent (corresponding to bounded distributive lattices).
- It is shown that the category Partial(FinStoch) is equivalent to the Kleisli category of a lifted distribution monad, which is an affine monad on a restriction category, thereby proving Partial(FinStoch) is a domain category.

Results

Theorem 5.2 & 5.4: Establish the equivalence between a monad being domain/mass preserving and its Kleisli category being a domain/mass category.
Theorem 5.13: Proves the decomposition: $Markov \iff Mass \land WeaklyMarkov$ .
Proposition 3.10: Demonstrates that a positive mass category is a restriction category, linking the new mass axiom to the classical restriction structure under positivity conditions.
Corollary 8.7 & 8.8: Show that if a domain category (or Markov category) is posetal oplax cartesian with respect to the canonical order, it collapses to a cartesian restriction category (or cartesian monoidal category, respectively).
Case Study Results: The paper confirms that the Kleisli category of relations over a Boolean semiring is a domain category, and that Partial(FinStoch) is a domain category, providing alternative proofs for these facts using the new machinery.

Significance
The paper claims to enrich the existing taxonomy of "categories for relations" by identifying and formalizing intermediate structures that were previously implicit in the behavior of Kleisli categories. By introducing mass and domain categories, the authors provide a more granular algebraic framework that explains why certain Kleisli categories (like those of affine monads on restriction categories) fail to be full restriction categories yet retain specific structural properties. This work distills the categorical presentation of probability and partiality, offering a unified perspective that connects gs-monoidal categories, Markov categories, and restriction categories through the lens of monad preservation and Kleisli lifting. The results clarify the relationship between affine monads and domain preservation, and between weakly Markov categories and the group structure of hom-sets, thereby refining the understanding of how probabilistic and partial structures arise from symmetric monoidal foundations.