💻 computer science

A Topological Framework for Finite Behavioural Observations and Verification

This paper establishes a topological framework for formal verification by demonstrating that properties verifiable through finite behavioural observations correspond precisely to open sets in the induced topologies, while characterizing the specific structures generated by trace, simulation, and bisimulation relations.

Original authors: Antonis Achilleos, Vasiliki Kyriakou

Published 2026-06-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonis Achilleos, Vasiliki Kyriakou

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 complex machine, like a robot or a software program, but you can't see its internal gears or code. You can only watch what it does. This paper is about how we can use those limited, "finite" glimpses of behavior to figure out if the machine is working correctly.

The authors, Antonis Achilleos and Vasiliki Kyriakou, use a branch of mathematics called topology (which studies shapes and spaces) as a giant map to organize these observations. Think of topology here not as rubber sheets, but as a way of sorting things into "neighborhoods" based on what we can see.

Here is the story of their findings, broken down into simple concepts:

1. The Problem: Seeing the Forest, Not the Trees

In computer science, we often want to verify if a system is "good." But we can't watch a system forever. We only get finite observations—short clips of what the system does.

The Analogy: Imagine trying to guess the plot of a movie by only watching 5-second clips. If you see a car chase, you know the movie has action. But if you only see a car, you don't know if it's driving, parked, or crashing.

The paper asks: What kind of "truths" can we confirm just by looking at these short clips?

2. The First Map: The "Trace" View (The Linear Path)

The simplest way to watch a machine is to just record the list of buttons it presses (its "traces").

The Analogy: Imagine a robot that walks in a straight line. You only see the footprints it leaves.
The Finding: If you only look at these footprints, the mathematical "map" (topology) you get is the Cantor Topology. This is a famous, well-behaved map where things are close to each other if they share a long history of footprints.
The Twist: If you try to look at the entire infinite history of footprints at once (Full Trace Inclusion), the map breaks down and becomes discrete. This means every single robot becomes its own isolated island. You can't compare them anymore because the requirement to match the entire infinite future is too strict. It's like saying two people are only "similar" if they have lived the exact same life from birth to death.

3. The Second Map: The "Simulation" View (The Branching Path)

The authors realized that just looking at footprints misses something crucial: Choices.

The Analogy: Imagine two robots.
- Robot A walks down a hallway, then reaches a fork. It can turn Left (to a door) OR Right (to a window).
- Robot B walks down the same hallway, then reaches a fork. It can turn Left (to a door) AND Right (to a window) at the same time (or has a mechanism to do both).
- If you only watch the footprints, both robots look identical: "Walk, Turn Left, Stop" and "Walk, Turn Right, Stop."
The Finding: The authors introduced a new map called $\tau_{sim}$ (Simulation Topology). This map uses "finite loop-free processes" as observations. Think of these as little flowcharts of choices.
- This new map can tell Robot A and Robot B apart because it sees the structure of the choices, not just the path taken.
- Result: This map is "finer" (more detailed) than the footprint map. It creates smaller, more specific neighborhoods.

4. The Golden Rule: Open Sets are "Verifiable Truths"

This is the paper's biggest theoretical breakthrough. They proved a general rule connecting math and verification:

The Rule: A property (like "The robot is safe") is verifiable using finite observations if and only if it is an "open set" on their map.
The Analogy: Imagine a "Safe Zone" on a map. If the zone is "open," it means you can stand anywhere inside it and take a small step (a finite observation) that guarantees you are still inside the zone. You don't need to see the whole map to know you are safe; a quick peek is enough.
If a property is not an open set, you can never be 100% sure it's true just by looking at a finite clip. You might always be on the very edge, waiting for the next second to confirm.

5. Applying the Rule: Monitorability

They applied this rule to their two maps:

On the Footprint Map ( $\tau_O$ ): The "verifiable" properties are those you can confirm by watching a few specific sequences of actions (Multi-trace monitorability).
On the Choice Map ( $\tau_{sim}$ ): The "verifiable" properties are those you can confirm by watching a few specific patterns of choices (Simulation monitorability).

6. The "Deadlock" Surprise

The authors tested what happens if they try to use even stricter rules, like "Complete Simulation" (which checks if a machine stops working, or "deadlocks").

The Problem: They found that if you try to use these stricter rules as a basis for the map, the map falls apart. It doesn't cover all the machines. Some machines run forever and never "stop," so they don't fit into the strict "stop-checking" categories.
The Solution: They found a middle ground called Finite-Depth Bisimulation. This is like checking if two robots behave the same way for exactly k steps.
The Result: This creates a brand new map ( $\tau_{fin}^{bis}$ $τ_{f in}^{bi s}$ ).
- The Key Difference: On this new map, you can actually spot a "deadlocked" robot (one that is stuck and does nothing). On the previous "Simulation" map, a stuck robot looked just like a robot that was about to move, because the simulation only checks if the stuck robot could be mimicked, not if it must be mimicked.
- In the new map, being "stuck" is a visible, distinct feature (a "clopen" set, meaning it's both open and closed).

Summary

The paper builds a mathematical framework where:

Finite observations (short clips of behavior) create maps (topologies).
Verifiable properties are exactly the open areas on these maps.
Looking at choices (simulation) gives you a more detailed map than just looking at paths (traces).
Looking at choices up to a certain depth (bisimulation) gives you a completely different map where "stuck" machines are clearly visible.

In short, the authors showed us that the way we choose to "watch" a system determines the mathematical landscape we use to verify it, and different ways of watching reveal different truths.

Technical Summary: A Topological Framework for Finite Behavioural Observations and Verification

Problem Statement
Formal verification and monitorability rely on finite observations to determine whether a system satisfies a property. While runtime verification and monitorability have been studied operationally, there is a need for a unified mathematical framework that characterizes exactly which properties can be confirmed using finite information. Existing work has established connections between the Cantor topology and trace-based monitorability, but a general theory linking arbitrary finite observations (including branching behavior) to verification capabilities is lacking. This paper addresses the question: Which properties can be confirmed from finite information, and how do different types of observations (traces, simulations, bisimulations) induce different topological structures on process spaces?

Methodology
The authors adopt a topological approach where finite observations are treated as the generators of a topology on a space of processes. The core methodology involves:

Defining Observation Spaces: Starting with specific types of finite observations (e.g., finite traces, finite loop-free processes) and defining the sets of processes that satisfy them.
Generating Topologies: Treating these satisfaction sets as basic open sets (or sub-basis elements) to generate a topology. The open sets in these topologies represent properties that can be "confirmed" by the corresponding observations.
Comparing Semantics: Analyzing how different behavioral relations (trace inclusion, simulation, bisimulation) induce distinct topologies. This involves comparing the expressiveness of the observations and the resulting topological structures (e.g., checking for strict inclusion, discreteness, or the ability to distinguish specific process behaviors like deadlocks).
Verification Theorem: Proving a general theorem linking the concept of "verifiability" (the ability to conclude a property holds based on finite evidence) directly to the topological concept of "openness."

Key Contributions and Results

Trace-Based Topologies:
- The paper analyzes full trace inclusion ( $\sqsubseteq_T$ ) on a process space. It shows that the Alexandroff topology induced by full trace inclusion on infinite traces ( $\Sigma^\omega$ ) is the discrete topology, meaning every subset is open.
- In contrast, when restricting observations to finite traces (finite prefixes), the induced topology coincides with the classical Cantor topology.
- The authors demonstrate that finite-depth trace inclusion (comparing traces up to length $k$ ) generates the same topology as finite trace observations, confirming that both capture identical finite-prefix information.
Process-Based Topologies ( $\tau_O$ vs. $\tau_{sim}$ ):
- For arbitrary Labelled Transition Systems (LTS), the authors define the trace observation topology ( $\tau_O$ ) generated by finite positive trace observations. They prove $\tau_O$ coincides with the topology induced by finite-depth trace inclusion.
- They introduce the simulation topology ( $\tau_{sim}$ ) generated by finite loop-free processes as observations. A process satisfies an observation if it simulates the finite loop-free process.
- Strict Refinement: The paper proves that $\tau_O \subsetneq \tau_{sim}$ . Simulation observations are strictly more expressive because they can distinguish processes with identical finite traces but different branching structures (e.g., distinguishing a process with a choice between $b$ and $c$ from one with a single state allowing both).
General Verification Theorem:
- The central theoretical result (Theorem 5.4) states that for any topology generated by a basis of finite observations, a property is verifiable (i.e., its satisfaction can be concluded from finite evidence) if and only if it is an open set in that topology.
- This unifies monitorability concepts:
  - Openness in $\tau_O$ corresponds to multi-trace monitorability (verifying a property by observing a finite set of traces).
  - Openness in $\tau_{sim}$ corresponds to simulation monitorability.
Limits of Stronger Relations:
- The authors investigate replacing simulation with stronger relations like complete simulation and ready simulation. They show that the families of observations for these relations fail to form a basis because they do not satisfy the covering property (they cannot cover processes that run forever without deadlocking).
- Consequently, these stronger relations cannot be used to generate observation topologies in the same manner on arbitrary LTSs.
Finite-Depth Bisimulation:
- The paper introduces finite-depth bisimulation observations. Unlike simulation, which is one-sided, finite-depth bisimulation checks behavior in both directions up to a bounded depth.
- This yields a topology ( $\tau_{bis}^{fin}$ ) that is genuinely different from $\tau_{sim}$ . Specifically, the set of deadlocked processes is clopen (both open and closed) in $\tau_{bis}^{fin}$ but not open in $\tau_{sim}$ . This demonstrates that finite-depth bisimulation captures finite behavioral information (specifically deadlock) that simulation observations miss.
Logical Characterization:
- The paper connects these topologies to Modal Logic (Hennessy-Milner Logic). It shows that the topologies $\tau_O$ , $\tau_{sim}$ , and $\tau_{bis}^{fin}$ can be generated by fragments of modal logic formulas (Trace Logic, Simulation Logic, and bounded HML, respectively), reinforcing the correspondence between logical definability and topological openness.

Significance and Claims
The paper claims to provide a "common standpoint" for relating behavioral semantics, finite verification, and monitorability through observation-induced topologies.

It establishes that the distinction between linear-time (trace) and branching-time (simulation/bisimulation) semantics is fundamentally a distinction in the topological structure of the process space induced by the available observations.
It clarifies the limits of finite verification: while simulation allows for a strictly finer topology than traces, moving to even stronger relations like complete simulation breaks the topological framework unless the observations are bounded (as in finite-depth bisimulation).
The work formalizes the intuition that "open sets are the properties we can verify," extending this principle from the classical Cantor setting to general process spaces and branching behaviors.

The authors note that future work could explore the specialization preorders of these topologies and extend the framework to include finite-state processes with loops, but the current contribution is strictly limited to finite, loop-free observations and their topological consequences.