💻 computer science

The complexity of being monitorable

This paper utilizes descriptive set theory to characterize the topological complexity of monitorable sets in countable spaces, demonstrating that while they form a $\Pi^0_3$ family in second countable spaces, they can reach $\Pi^1_1$ -complete complexity in non-second countable spaces.

Original authors: Riccardo Camerlo, Francesco Dagnino

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Riccardo Camerlo, Francesco Dagnino

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 watching a movie, but you can only see it one frame at a time. You are a monitor. Your job is to watch the movie (the system's behavior) and decide: "Is this movie following the script?" or "Is it breaking the rules?"

Sometimes, you can tell immediately. If the script says "The hero must never fall," and you see the hero fall in the first frame, you can shout, "Violation!" immediately. If the script says "The hero must eventually fly," and you see them fly, you can shout, "Satisfaction!"

But what if the script is tricky? What if the hero is standing on a cliff edge, and you can't see if they will jump or stay? You keep watching frame by frame, but no matter how long you watch, you can never be 100% sure if they are going to jump or not. You are stuck in limbo. In the world of computer science, a property that traps a monitor in this "never-ending guess" state is called unmonitorable.

This paper, by Riccardo Camerlo and Francesco Dagnino, asks a very specific question: How hard is it to figure out if a rule (a property) is one of these "stuck" rules or a "solvable" one?

They treat the possible behaviors of a system like points in a geometric space. They use a branch of math called Descriptive Set Theory (think of it as a "complexity ruler") to measure how difficult it is to sort these rules into "solvable" and "unsolvable" piles.

Here is the breakdown of their findings, using simple analogies:

1. The "Well-Behaved" World (Second Countable Spaces)

Imagine a world where the rules of the game are simple and organized, like a library with a clear catalog system. In math terms, this is a second countable space.

The Finding: In this organized world, the list of "solvable rules" (monitorable sets) is never too complicated. It sits at a specific, manageable level of difficulty (mathematically called $\Pi^0_3$ ).
The Analogy: Think of this like a puzzle box. You know the box has a specific number of layers. You might need to open three layers to find the answer, but you know you will never need to open a million layers. The complexity is "moderate."
The Twist: Even within this organized world, some rule sets are "simple" (easy to sort), while others are "hard" (requiring the maximum three layers of logic). The authors provide a checklist to tell you which kind of puzzle box you are holding.
- Simple Case: If the space has "isolated points" (like a room with a single, distinct chair), almost everything is solvable.
- Hard Case: If the space is a dense web of connections (like a crowded subway station where everyone is touching everyone), sorting the rules becomes the hardest possible task allowed in this organized world.

2. The "Chaotic" World (Non-Second Countable Spaces)

Now, imagine a world where the rules are chaotic, with no clear catalog, and connections are infinite and tangled. In math terms, this is a non-second countable space.

The Finding: Here, the complexity explodes. The list of "solvable rules" can become infinitely more complex than in the organized world.
The Analogy: In the organized world, you were solving a puzzle with a known number of layers. In this chaotic world, the puzzle box has a bottomless pit. You might need to check an infinite number of layers just to decide if a rule is solvable.
The Result: The authors show an example where the complexity reaches a level called $\Pi^1_1$ -complete. In plain English, this means the problem is so difficult that it is as hard as the hardest problems imaginable in this field of math. It's the difference between solving a Sudoku and trying to solve a riddle that requires knowing the answer to a riddle that requires knowing the answer to... forever.

3. The "Real-World" Test (Transition Relations)

The authors also looked at a specific type of system used in computer science: automata (machines that change states based on events, like a traffic light or a video game character).

The Finding: They looked at all possible ways these machines could be built. They found that most of them (in a mathematical sense called "Baire category") fall into the "Simple" category.
The Analogy: If you randomly build a machine, it is overwhelmingly likely to be a "well-behaved" machine where you can easily tell if the rules are solvable. The "chaotic, infinitely complex" machines are the rare exceptions, like finding a unicorn in a forest.

Summary

The Goal: To understand how hard it is to tell if a computer system's rules can be effectively checked by a monitor.
The Organized World: If the system's behavior space is "nice" and organized, the difficulty is predictable and manageable (Level 3 on the complexity scale).
The Chaotic World: If the system's behavior space is messy and unstructured, the difficulty can skyrocket to the absolute limit of what is mathematically possible.
The Good News: Most real-world systems (modeled as transition relations) fall into the "nice" category, meaning their monitorability is usually a solvable problem.

The paper doesn't tell us how to build better monitors for specific industries; rather, it draws a map of the mathematical landscape, showing us where the easy paths are and where the cliffs of infinite complexity lie.

Technical Summary: The Complexity of Being Monitorable

Problem Statement
Runtime Verification (RV) relies on synthesizing monitors to determine whether system executions satisfy or violate a specification. A central challenge is monitorability: the property that a specification allows for the synthesis of a monitor capable of eventually reaching a verdict (satisfaction or violation) based on observed executions. While monitorability is often studied syntactically for specific specification languages, Diekert and Leucker [DL14] proposed a semantic, topological approach. In this framework, system behaviors are points in a topological space $X$ , and observations are open sets. A property (a subset $A \subseteq X$ ) is monitorable if, for every non-empty open observation $U$ , one can refine it to a non-empty open $V \subseteq U$ that is entirely contained in $A$ or entirely in its complement.

The paper addresses the descriptive set-theoretic complexity of the family of monitorable sets, denoted $M(X)$ , viewed as a subset of the powerset $\mathcal{P}(X)$ . Specifically, the authors investigate how difficult it is to determine whether an arbitrary subset of a countable space $X$ is monitorable. They analyze the position of $M(X)$ within the Borel hierarchy and the projective hierarchy, depending on the topological properties of $X$ .

Methodology
The authors employ tools from descriptive set theory [Kec95] and Wadge reducibility.

Topological Setup: They identify $\mathcal{P}(X)$ with the Cantor space $2^X$ (via characteristic functions) endowed with the product topology. Since $X$ is countable, $\mathcal{P}(X)$ is a Polish space.
Characterization of Monitorability: They utilize the characterization that a set $A$ is monitorable if and only if the interior of its frontier is empty ( $\text{Int}(\text{Fr}(A)) = \emptyset$ ). This is equivalent to saying $A$ is not both dense and codense in any non-empty open set.
Complexity Analysis: They classify $M(X)$ by determining if it belongs to specific pointclasses ( $\Sigma^0_\alpha, \Pi^0_\alpha, \Sigma^1_1, \Pi^1_1$ ) and whether it is complete for those classes. This involves constructing continuous reductions from known hard sets (e.g., $\Sigma^0_3$ -complete or $\Pi^1_1$ -complete sets) to $M(X)$ .
Case Distinction: The analysis is split into two primary cases:
- Second Countable Spaces: Where $X$ has a countable basis.
- Non-Second Countable Spaces: Where $X$ is countable but lacks a countable basis.

Key Contributions and Results

1. The Second Countable Case
For a countable, second countable topological space $X$ , the family $M(X)$ is always a $\Pi^0_3$ subset of $\mathcal{P}(X)$ . The paper provides a precise classification of the possible complexities $M(X)$ can attain:

$\Delta^0_1$ (Clopen): Occurs if $M(X) = \mathcal{P}(X)$ , which happens if and only if the set of isolated points is dense in $X$ .
$\Sigma^0_2$ -complete: Occurs in spaces like the cofinite topology on a countable set.
$\Pi^0_3$ -complete: Occurs in spaces such as the Alexandrov topology on $\mathbb{N}^2$ with a specific partial order.
Impossibility Results: The authors prove that for second countable spaces, $M(X)$ cannot be $\Sigma^0_1$ -complete, $\Delta^0_2$ -sharp, or $\Pi^0_2$ -complete.

A crucial operational criterion is derived (Remark 3.15): $M(X)$ is $\Pi^0_3$ -complete if and only if, after removing the union of all minimal non-empty open sets, the remaining interior contains infinitely many pairwise disjoint open subsets. Otherwise, $M(X)$ is $\Sigma^0_2$ .

2. Application to Transition Relations
The authors apply these results to topologies induced by transition relations on a countable set of states (modeling branching-time systems). They define $R_0$ as the set of transition relations inducing a $\Sigma^0_2$ family of monitorable sets, and $R_1$ as those inducing a $\Pi^0_3$ -complete family.

Theorem 3.18: Both $R_0$ and $R_1$ are Borel subsets of the space of all transition relations. Furthermore, $R_0$ is comeagre (residual), meaning that "most" transition relations (in the sense of Baire category) induce a topologically simple family of monitorable sets ( $\Sigma^0_2$ ).

3. The Non-Second Countable Case
The paper demonstrates that the restriction to second countable spaces is essential.

Example: The authors construct a countable, non-second countable space (based on the Scott topology on finite sequences with a top element $\infty$ ).
Result: For this space, the family of monitorable sets $M(X)$ is $\Pi^1_1$ -complete (complete coanalytic). This represents a significant jump in complexity compared to the second countable case, showing that without second countability, the problem of determining monitorability can be as hard as the problem of well-foundedness of trees.

Significance
The paper provides a unifying, syntax-independent framework for understanding monitorability. By mapping the problem to descriptive set theory, it establishes that:

In the standard setting of second countable spaces (which includes many models of runtime verification), the complexity of determining monitorability is bounded within the Borel hierarchy, specifically at the $\Pi^0_3$ level.
There is a clear structural criterion (related to minimal open sets and disjointness) that determines whether a specific system model yields a "simple" ( $\Sigma^0_2$ ) or "complex" ( $\Pi^0_3$ -complete) monitorability problem.
The assumption of second countability is critical; relaxing it allows for arbitrarily high complexity (up to $\Pi^1_1$ -complete), highlighting the importance of topological constraints in the theoretical analysis of runtime verification.

The work does not propose new algorithms for monitor synthesis but rather delineates the theoretical limits and structural properties of the monitorability decision problem across different topological models.

1. The "Well-Behaved" World (Second Countable Spaces)

2. The "Chaotic" World (Non-Second Countable Spaces)

3. The "Real-World" Test (Transition Relations)

Summary

Technical Summary: The Complexity of Being Monitorable

More like this