💻 computer science

Bisimulations and Modal Logics for Higher Dimensional Automata

This paper introduces new intermediate behavioral equivalences and a novel modal logic that successfully characterizes hereditary history-preserving (hhp) bisimilarity, the finest equivalence in van Glabbeek's spectrum for Higher-Dimensional Automata, for the first time.

Original authors: Safa Zouari, Rob van Glabbeek, Krzysztof Ziemiański

Published 2026-08-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Safa Zouari, Rob van Glabbeek, Krzysztof Ziemiański

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 describe a dance. If you only write down who steps forward and who steps back, you've captured a simple sequence, like a line of people waiting for a bus. But what if the dance involves two people spinning at the exact same time, or three people weaving around each other without ever touching? This is the world of "true concurrency." In computer science, we often try to explain complex, multi-tasking systems by pretending everything happens one tiny step after another (like a fast-forwarded video). But real computers, and even our own brains, often do many things at once. To understand these systems, scientists use geometric models called Higher-Dimensional Automata (HDAs). Think of these not as flat maps, but as multi-layered sculptures where a single point represents a start, a line represents one action, a square represents two actions happening together, and a cube represents three.

The big question in this field is: How do we tell if two different sculptures represent the same underlying dance? If two dancers perform the same moves but in a slightly different order, are they doing the same thing? If one dancer takes a shortcut through a crowd while another walks around the edge, is that a different performance? Scientists have developed a "spectrum" of answers, ranging from very strict rules (where every tiny detail must match) to very loose rules (where only the final result matters). The strictest rule, called hereditary history-preserving (hhp) bisimilarity, is the gold standard. It demands that the systems match not just in what they do, but in when they do it, why they do it, and how their history of choices connects to their future. However, for decades, no one could write a simple "checklist" or a logical language to prove that two HDAs matched this strictest rule. It was like having a perfect definition of a masterpiece painting but no way to describe it with words.

This paper, titled "Bisimulations and Modal Logics for Higher Dimensional Automata," finally cracks that code. The authors, Safa Zouari, Rob van Glabbeek, and Krzysztof Ziemiański, introduce a new way to look at the paths a system can take through its geometric sculpture. They realized that the old way of comparing paths was like bundling two different types of moves into one messy package. They decided to untie the knot. They split the comparison into two distinct moves: similarity (swapping the order of two independent steps, like two people swapping places in a line without bumping into anyone) and subsumption (taking a shortcut through a high-dimensional "hole" in the sculpture, effectively doing two things at once instead of one after the other).

By separating these moves, the authors discovered a whole new family of "middle-ground" rules. Imagine a ladder where the bottom rung is "ST-bisimilarity" (a loose rule that only cares about the start and end of actions) and the top rung is "hhp-bisimilarity" (the strict rule that cares about everything). Before this paper, there were big gaps between the rungs. The authors filled those gaps with new, intermediate rules like semi-history-preserving and quasi-history-preserving bisimilarity. These new rules let us say, "These two systems are the same if we ignore shortcuts but care about order," or "They are the same if we care about shortcuts but ignore order."

The most exciting part is that the authors didn't just find these new rules; they built a modal logic for each one. Think of modal logic as a special language of "can" and "must." With this new language, you can write a sentence that says, "There exists a path where action A starts, and if you take a shortcut here, you cannot do action B." The paper proves that for every single rule on their new ladder, there is a corresponding sentence in this logic that perfectly describes it. Most importantly, they provided the first-ever logical description for the strictest rule, hhp-bisimilarity. This means we can now use a precise, mathematical language to verify if two complex, multi-tasking systems are truly identical in their history and structure, even when they are running in parallel. This is a major step forward for verifying security and privacy in systems where things happen simultaneously, ensuring that the "dance" of our digital world is performed exactly as intended.

Technical Summary: Bisimulations and Modal Logics for Higher Dimensional Automata

Problem Statement

Higher-Dimensional Automata (HDAs) provide a geometric model of true concurrency where $n$ -dimensional cells represent the simultaneous execution of $n$ independent events, avoiding the reduction of concurrency to interleaving. HDAs serve as a unifying semantic framework for various non-interleaving concurrency models (e.g., Petri nets, event structures) up to hereditary history-preserving (hhp) bisimilarity.

Despite HDAs being introduced 35 years ago, a significant gap remains in the theoretical characterization of their behavioral equivalences via modal logic. While hhp-bisimilarity is the finest behavioral equivalence in van Glabbeek's spectrum, respecting both branching time and causality, no modal logic has previously provided an exact characterization of it on HDAs. Previous attempts, such as Prisacariu's Higher-Dimensional Modal Logic, failed to characterize even ST-bisimilarity, and recent work by Zouari, Ziemiański, and Fahrenberg only succeeded in characterizing ST-bisimilarity in the absence of autoconcurrency.

Methodology

The paper employs a decomposition of the classical path adjacency relation and a generalization of the Hennessy-Milner theorem to address the characterization problem.

1. Decomposition of Path Adjacency

The authors decompose the classical $\ell$ -adjacency relation on paths (originally defined in [12]) into two conceptually distinct components:

$\ell$ -Similarity ( $\Leftrightarrow_\ell$ ): A symmetric operation that permutes two adjacent independent start phases or two adjacent end phases of events.
$\ell$ -Subsumption ( $\sqsubseteq_\ell$ ): A directional operation that replaces a sequential traversal around a higher-dimensional cell with a path passing directly through it, thereby increasing the degree of observed concurrency. Its inverse is unsubsumption ( $\sqsupseteq_\ell$ ).

By separating these operations, the authors can define bisimulation relations that require subsumption in only one direction, allowing for a finer control over preserved behavioral information than the original symmetric adjacency formulation.

2. The (I, M)-System Framework

To provide uniform modal characterizations, the authors introduce a transformation of HDAs into a specific type of labeled transition system called an (I, M)-system.

States: The paths of the HDA.
Labels: The ST-trace of the path (recording action starts, ends, and causal pairings).
Transitions: Relations defined by a subset $I$ of operations: path extension ( $\rightarrow$ ), subsumption ( $\sqsubseteq$ ), unsubsumption ( $\sqsupseteq$ ), similarity ( $\Leftrightarrow$ ), and path restriction ( $\leftarrow$ ).

This framework allows the application of a generalized Hennessy-Milner theorem, proving that for any choice of index set $I$ and label set $M$ , bisimilarity and logical equivalence coincide.

Key Contributions

1. A Spectrum of Intermediate Bisimilarities

Using the decomposition of adjacency, the paper introduces a family of intermediate bisimulation equivalences that strictly sit between ST-bisimilarity and hhp-bisimilarity. These are parameterized by the subset of operations required in the bisimulation relation. Key new notions include:

Semi-history-preserving (shp) bisimilarity: Requires path extension and subsumption.
Quasi-history-preserving (qhp) bisimilarity: Requires path extension, subsumption, and similarity.
Hereditary variants: Including path restriction (e.g., hshp, hqhp).
Restricted variants: Such as $\leftrightarrow_{reST}$ (requiring similarity and restriction) and $\leftrightarrow_{ureST}$ (requiring similarity and unsubsumption).

2. Strict Inclusion Hierarchy

The authors establish a hierarchy of these equivalences. Using explicit separating examples (e.g., Figures 4, 5, 6, 7, 9, 10), they prove strict inclusions between most pairs of these equivalences.

For instance, $\leftrightarrow_{shp} \subsetneq \leftrightarrow_{ST}$ and $\leftrightarrow_{qhp} \subsetneq \leftrightarrow_{shp}$ .
The paper identifies specific cases where inclusion holds but a separating example is not provided (e.g., between certain hereditary variants), posing these as open questions regarding whether the equivalences coincide.

3. Exact Modal Characterizations

By instantiating the (I, M)-system framework to HDAs, the paper derives exact modal characterizations for every bisimilarity in the spectrum.

Each equivalence corresponds to a natural fragment of a single modal language.
The logic for hhp-bisimilarity ( $L_{hhp}$ ) is the first modal logic to exactly characterize hhp-bisimilarity on HDAs, including in the presence of autoconcurrency.
Logics for coarser equivalences are shown to be syntactic fragments of those for finer equivalences.

Results

Theoretical Unification: The paper unifies the characterization of ST-bisimilarity, hp-bisimilarity, and hhp-bisimilarity, along with intermediate notions, under a single modal framework.
Separation of Concepts: The decomposition of adjacency reveals that similarity and subsumption are independent behavioral conditions. This allows for the definition of equivalences that distinguish systems based on their capacity for concurrency refinement versus the symmetry of their concurrent structure.
Counterexamples: The paper provides concrete HDA examples demonstrating that:
- ST-bisimilarity does not imply shp-bisimilarity (systems can have the same ST-traces but differ in subsumption capabilities).
- shp-bisimilarity does not imply qhp-bisimilarity (systems can differ in their ability to permute events).
- hp-bisimilarity does not imply hhp-bisimilarity (distinguishing hereditary from non-hereditary properties).

Significance

The paper claims significance in providing the first exact modal characterizations of the full spectrum from ST- to hhp-bisimilarity on HDAs.

The authors highlight the practical relevance of this finer spectrum in the verification of security protocols. Citing Aubert, Horne, and Johansen [1, 2], they note that moving to finer non-interleaving bisimilarity notions expands the class of detectable attacks on privacy protocols. The intermediate equivalences introduced, each accompanied by a characterizing modal logic, offer a principled way to calibrate the attacker model between ST- and hhp-bisimilarity. This allows for the potential detection of attacks that are beyond ST-bisimilarity without requiring the full strength (and potentially higher complexity) of hhp-bisimilarity.

The work establishes a foundation for future verification tools that can leverage these intermediate logics to balance precision and computational feasibility in the analysis of concurrent systems.