💻 computer science

Generalised Möbius Categories and Convolution Kleene Algebras

This paper establishes a construction for convolution Kleene algebras on generalised Möbius categories by defining a suitable star operation, thereby enabling algebraic reasoning and verification for weighted, probabilistic, and concurrent programs as well as higher-dimensional rewriting.

Original authors: James Cranch, Georg Struth, Jana Wagemaker

Published 2026-02-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: James Cranch, Georg Struth, Jana Wagemaker

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 a city planner trying to understand the flow of traffic, the spread of information, or the execution of a complex computer program. You need a mathematical tool that can handle not just simple "yes/no" decisions, but also weights (like distance, cost, or probability) and sequences (like a series of steps taken to get from point A to point B).

This paper introduces a powerful new mathematical toolkit called Convolution Kleene Algebras. To understand it, let's break it down using a few everyday analogies.

1. The Problem: Counting the Infinite

Imagine you are trying to calculate the "best" way to get from your house to a friend's house.

The Map (The Structure): You have a map with roads (arrows) and intersections (objects).
The Costs (The Values): Every road has a cost (time, money, or a probability of getting stuck).
The Goal: You want to find the total cost of all possible routes, including routes that loop around, take detours, or repeat steps.

In math, this is called a Convolution Algebra. It's like mixing ingredients (the costs of individual roads) to create a new recipe (the total cost of a journey).

The Catch: If your map has loops (you can drive in circles forever), the number of possible routes is infinite. If you try to add up an infinite number of costs, your calculator (or the math) might break. Traditional methods often require the map to be very simple (like a straight line) to avoid this infinite loop problem.

2. The Solution: The "Möbius" Filter

The authors introduce a special type of map called a Generalised Möbius Category.

Think of a Möbius strip (a loop with a twist). In this context, it doesn't mean the map is twisted in a weird way; it means the map has a very specific, orderly structure.

The Rule: On these maps, even if you can go in circles, you can only break a journey down into a finite number of steps in a meaningful way.
The Analogy: Imagine a recipe book. A normal book might have a recipe that says, "Add a pinch of salt, then add a pinch of salt, then add a pinch of salt... forever." That's useless. A Möbius recipe says, "You can repeat steps, but every time you repeat, the dish gets closer to being finished, and there's a limit to how many times you can repeat before the dish is done."

This "orderly" structure allows the mathematicians to use a recursive definition (a formula that calls itself) to calculate the total cost without getting stuck in an infinite loop.

3. The Magic Ingredient: The "Star" Operation

In computer science, there is a special symbol called the Kleene Star ( $*$ ). Think of it as a "Do-It-As-Many-Times-As-You-Need" button.

If you have a step "Walk to the store," the star operation ( $Walk^*$ ) means "Walk to the store, or walk there twice, or three times, or zero times." It represents repetition.

The big breakthrough in this paper is showing how to press this "Do-It-As-Many-Times-As-You-Need" button on these complex, weighted maps (categories) without the math exploding.

They use a clever trick invented by Kuich and Salomaa (think of them as the "Grandmasters of Recursion"). They define the star not as "add everything up forever," but as a step-by-step recipe:

Start with the direct path.
Add paths that take one detour.
Add paths that take two detours.
Because the map is a Möbius category, you know you will eventually run out of new detours to add. The sum stops naturally.

4. Why This Matters: Real-World Applications

Why should a regular person care? Because this math is the engine behind verifying that complex systems work correctly.

Software Verification: Imagine you are writing code for a self-driving car. You need to prove that no matter what traffic patterns occur (loops, detours, infinite waiting), the car will eventually stop at the red light. This new algebra helps prove that the "loops" in the code are safe and finite.
Probabilistic Programs: Imagine a weather app that predicts rain. It doesn't just say "Rain" or "No Rain"; it says "30% chance." This algebra can handle those percentages as it calculates the probability of a sequence of events (e.g., "It rains, then the bus is late, then I miss the meeting").
Higher Dimensions: The paper also talks about "3D" and "4D" maps (higher categories). Imagine not just a road map, but a map of how ideas interact, or how teams collaborate. This math helps organize those complex, multi-layered interactions.

Summary Analogy: The Infinite Buffet

Imagine a buffet where you can keep eating forever.

Old Math: If you try to calculate the total calories of an infinite buffet, you get infinity. It's not useful.
This Paper's Math: It introduces a rule that says, "You can keep eating, but every time you take a bite, you get slightly fuller, and there's a limit to how many bites you can take before you are full."
The Result: You can now calculate the exact total calories of your meal, even though the buffet was theoretically infinite. You can also figure out the "best" meal (the one with the most flavor for the least calories) using a recursive recipe.

In a nutshell: The authors have built a new mathematical "calculator" that can handle complex, looping, weighted systems (like software or networks) by ensuring the loops are "tame" enough to be calculated step-by-step. This allows computer scientists to rigorously prove that their complex, probabilistic, and concurrent programs will behave correctly.

1. Problem Statement

Convolution algebras are fundamental structures in mathematics and computer science, formed by mapping a structure $X$ (such as a monoid, category, or relational monoid) into a value algebra $V$ (such as a semiring, ring, or field). While convolution algebras based on Kleene algebras (additively idempotent semirings equipped with a Kleene star operation) are crucial for program verification, path algorithms, and concurrency, a significant obstacle has hindered their construction on a wide class of structures: the definition of a suitable Kleene star.

Previous constructions were limited to:

Structures with a single identity element (e.g., free monoids).
Value algebras that were not necessarily Kleene algebras.
Quantales (complete lattices with multiplication), where the star is defined as an infinite supremum of powers ( $\bigvee_{i \ge 0} f^i$ ). This approach fails for semirings that lack infinite suprema or for applications requiring finite, inductive reasoning.

The core problem is how to define a recursive Kleene star on convolution algebras over categories with multiple objects (or relational monoids) such that the resulting algebra satisfies the axioms of a Kleene algebra, specifically enabling inductive proofs and finite computation.

2. Methodology

The authors employ a combination of category theory, algebraic logic, and combinatorial methods to solve this problem.

Generalisation of Möbius Categories: The authors introduce Möbius catoids (a generalisation of Möbius categories to relational monoids). A catoid is a set equipped with a set-valued composition operation. A catoid is "Möbius" if:
1. Every element has a finite number of 2-decompositions (finitely 2-decomposable).
2. Every identity element is indecomposable.
3. The structure satisfies a "saturated chain" property regarding source/target maps.
  These conditions ensure that every element has a finite "length" $\ell(x)$ , allowing for induction.
Recursive Star Definition: Instead of defining the star as an infinite sum (as in quantales), the authors adapt the classical recursive definition of the Kleene star for formal power series by Kuich and Salomaa. For a function $f: C \to K$ (where $K$ is a Kleene algebra) and an arrow $x$ in a Möbius catoid $C$ :
- For identity arrows $e$ : $f^*(e) = f(e)^*$ .
- For non-identity arrows $x$ :
  $f^*(x) = f(s(x))^* \cdot \sum_{x = y \odot z, y \neq s(x)} f(y) \cdot f^*(z)$
  Here, $s(x)$ is the source of $x$ . The sum is finite due to the Möbius condition, and the recursion is well-founded on the length $\ell(x)$ .
Structural Extensions: The methodology extends beyond basic Kleene algebras to:
- Modal Kleene Algebras: Adding domain and codomain operators.
- Conway Semirings: Using equational star axioms.
- Higher Dimensions: Generalising to $n$ -catoids and $n$ -Kleene algebras for higher-dimensional rewriting.

3. Key Contributions

Theoretical Foundation (Theorem 5.2): The primary result proves that the convolution algebra of maps from a Möbius catoid to a Kleene algebra forms a Kleene algebra under the recursive star definition. This generalises previous results that were restricted to single-object structures.
Unification of Concepts: The paper demonstrates that the Möbius condition is the precise structural requirement needed to make the Kuich-Salomaa recursive star work for categories and relational monoids, bridging the gap between incidence algebras (Rota) and Kleene algebra theory.
Extensions to Advanced Structures:
- Kleene Algebras with Tests: Showing that these convolution algebras naturally form Kleene algebras with tests (Theorem 6.6), a formalism essential for program verification (Hoare logic).
- Modal and Concurrent Algebras: Constructing modal convolution Kleene algebras (Section 7) and concurrent/interchange convolution Kleene algebras on Möbius 2-catoids (Section 8).
- Higher-Dimensional Algebras: Defining convolution $n$ -Kleene algebras on Möbius $n$ -catoids (Section 9), providing a framework for higher-dimensional rewriting systems.
Comparison with Quantales: The paper clarifies the relationship between convolution Kleene algebras and convolution quantales. While quantales work on arbitrary catoids using infinite sups, Kleene algebras require the finiteness provided by Möbius conditions but offer better properties for finite, generator-based reasoning (e.g., rational power series).

4. Key Results and Examples

Formal Power Series & Languages: The construction recovers the standard Kleene algebra of formal power series on free monoids and shuffle languages as special cases.
Interval Temporal Logics: The construction yields incidence Kleene algebras on categories of closed intervals. This supplies a missing "chop-star" operator for quantitative interval temporal logics and duration calculi, which previously lacked a Kleene algebraic treatment with finite sups.
Path Algorithms: For path categories on finite graphs, the star computes optimal path weights (e.g., shortest paths) via the recursive formula, generalising Aho-Hopcroft-Ullman algorithms.
Limitations: The recursive star is not suitable for structures lacking a non-trivial length notion, such as pair groupoids (weighted relations/matrix algebras), where the star must be defined via matrix decomposition (Conway's algorithm) rather than recursion.

5. Significance and Applications

The paper provides a robust algebraic foundation for quantitative program verification and higher-dimensional rewriting.

Program Verification: By enabling Kleene algebras with tests and modal operators on complex structures (like intervals or guarded strings), the work supports the development of quantitative Hoare logics and predicate transformer algebras. This allows for the verification of weighted, probabilistic, and concurrent programs.
Concurrency: The construction of concurrent convolution Kleene algebras on Möbius 2-catoids provides an algebraic semantics for interleaving and partial-order semantics in concurrent systems, extending beyond simple interleaving to structured concurrency.
Higher-Dimensional Rewriting: The $n$ -Kleene algebra construction offers a new tool for proving coherence properties (like Newman's Lemma) in higher-dimensional rewriting systems (polygraphs), where weights can be assigned to cells of various dimensions.
Algorithmic Efficiency: Unlike quantales which rely on infinite suprema, the Möbius-based approach ensures finite sums, making the algebras more suitable for implementation in algorithms and complexity analysis.

In summary, the paper successfully lifts the theory of Kleene algebras from simple monoids to a broad class of categorical and relational structures by identifying Möbius catoids as the natural setting for recursive star operations, thereby opening new avenues for algebraic reasoning in complex computational systems.