Forgetting Event Order in Higher-Dimensional Automata

Here is an explanation of the paper "Forgetting Event Order in Higher-Dimensional Automata," translated into simple language with creative analogies.

The Big Picture: The "Traffic Jam" of Computer Science

Imagine you are trying to describe a busy intersection where cars (events) are moving. In traditional computer science models, we often force these cars to line up in a single file, even if they are actually driving on different lanes at the same time. We say, "Car A went first, then Car B," even though they were side-by-side.

This paper argues that this "single file" rule is a fake constraint. It's an artificial order we invented to make the math easier, but it doesn't reflect reality. When we force independent events into a strict line, we create confusion, logical errors, and make it hard to compare different systems.

The authors propose a new way to look at these systems: Forget the line. Instead, let's just look at who is doing what and who is waiting for whom, without forcing a "first, second, third" order on things happening at the same time.

The Problem: The "Artificial Line"

The Analogy: The Strict Teacher
Imagine a strict teacher (the old model) who watches two students, Alice and Bob, working on separate projects.

Reality: Alice and Bob are working at the same time. They don't need each other.
The Teacher's Report: "Alice started at 9:00. Bob started at 9:01. Therefore, Alice is 'before' Bob."

The teacher is inventing a timeline that doesn't exist. If you ask the teacher, "Did Bob start before Alice?" they might say "No," because they forced a rule that says "If two things happen at the same time, we must pick one to be first."

Why this is bad:

It breaks symmetry: If you swap Alice and Bob, the teacher's report changes completely, even though the reality (two people working together) is identical.
It confuses logic: If you try to write a rule like "Alice and Bob are working," the teacher's system might say, "No, that's impossible because I decided Alice is first."
It doesn't match other models: Other ways of modeling computers (like Petri nets) don't force this line. So, trying to translate between them is like trying to translate a poem into a language that doesn't have words for "simultaneous."

The Solution: The "Interval Map"

The authors suggest a new way to record the story, which they call Interval Ipomsets.

The Analogy: The Concert Schedule vs. The Setlist

Old Way (ST-Trace): Like a setlist that says: "Song 1 starts, Song 2 starts, Song 1 ends, Song 2 ends." It forces a specific order of events.
New Way (Ipomset): Like a concert schedule that shows intervals.
- Song 1: Starts at 8:00, ends at 8:15.
- Song 2: Starts at 8:05, ends at 8:20.
- Visual: You see two overlapping bars. You know Song 2 started while Song 1 was still playing. You don't need to say "Song 1 is #1 and Song 2 is #2." You just see the overlap.

In this new model, if you swap the names of the songs, the visual picture of the overlap stays exactly the same. The "order" is gone; only the relationships (who overlaps whom) remain.

The Magic Trick: Symmetrization

The paper does something clever called Symmetrization.

The Analogy: The Mirror Room
Imagine you have a room with a single chair (the old model). If you walk in from the left, it looks different than if you walk in from the right.
The authors say: "Let's build a mirror room." Now, for every chair, there is a mirror image. If you walk in from the left, you see the chair. If you walk in from the right, you see the mirror image.

In the math, this means they take their system and create a "symmetric version" where every possible arrangement of events exists.

The Result: They prove that the "Mirror Room" (the new, order-free model) is mathematically identical to the "Symmetric Expansion" of the old model.
Why it matters: This proves that their new "forgetting the order" approach isn't just a guess; it's the true underlying reality of these systems. It works for every computer system, not just the simple ones.

The Payoff: Why Should You Care?

The authors show that by dropping the artificial "first/second" rule, three major problems disappear:

Fairness (Symmetry): It no longer matters if you list events as "A then B" or "B then A." The system treats them as the same. It's like saying "Left and Right" are just directions, not a hierarchy.
Better Logic: You can now write rules (logic) that say "A and B happen together" without the computer getting confused and saying, "But I decided A is first!"
Universal Translator: It finally allows computer scientists to translate between different models (like Petri nets and HDAs) without losing information. It's like finally finding a dictionary that works for all languages, not just the ones that speak English.

Summary

The Old Way: "Everything must happen in a single line, even if it doesn't need to. This creates fake rules and confusion."
The New Way: "Let's draw a map of who is doing what and when they overlap. We ignore the fake line. This makes the math cleaner, the logic fairer, and the models compatible."

The paper is essentially saying: "Stop forcing the universe into a queue. Let things happen in parallel, and build your math to match that reality."

Here is a detailed technical summary of the paper "Forgetting Event Order in Higher-Dimensional Automata" by Safa Zouari.

1. Problem Statement

Higher-Dimensional Automata (HDAs) are a geometric model for true concurrency, where higher-dimensional cells represent independent events occurring simultaneously. However, the standard formulation of HDAs relies on ordered combinatorial structures (specifically, labeled event lists with a strict total order). This introduces an artificial "event order" that is not part of the observable behavior of the system.

Key Issues Identified:

Representational Artifacts: The imposed event order creates a mismatch between the combinatorial structure of HDAs and their observable behavior. It distinguishes between executions that are observationally equivalent (e.g., distinguishing $a \parallel b$ from $b \parallel a$ ).
Logical Asymmetries: In temporal and modal logics, this artificial order breaks symmetry. A formula might accept $a \parallel b$ but reject $b \parallel a$ , even though these are indistinguishable in true concurrency.
Categorical Mismatch: The standard ordered presentation complicates the application of categorical tools, specifically the Open Maps framework used to derive modal logics characterizing hereditary history-preserving (hhp) bisimulation. The reliance on ST-traces lacks the necessary path-category structure for a canonical application of this framework.
Incompatibility with Other Models: Injecting behaviors from models like Petri nets (which are naturally unordered) into ordered HDA frameworks leads to systematic mismatches.

2. Methodology

The paper proposes a shift from ordered HDAs to order-free (symmetric) HDAs, grounded in category theory and presheaf semantics.

A. Base Categories and Symmetrization

Ordered Base ( $\square$ ): The standard category of labeled precubical sets using "conclists" (concurrency lists with a strict total order).
Symmetric Base ( $\Xi$ ): A new base category using "concsets" (concurrency sets) where events have labels but no inherent order.
Generator-Based Equivalence ( $\Xi_g$ ): The author introduces $\Xi_g$ , a category generated by coface maps and permutation morphisms acting on ordered structures.
Key Theorem: The paper proves that $\Xi_g$ is categorically isomorphic to $\Xi$ . This demonstrates that "adding symmetries" (permutations) to an ordered structure is mathematically equivalent to "forgetting the event order." This allows the authors to treat symmetric HDAs as the canonical form for all HDAs.

B. Semantics via Interval ipomsets

Ipomsets: The paper adopts interval ipomsets (partially ordered multisets with interfaces) as the semantic label for execution paths.
Order-Free Labeling: Unlike previous works that retained event order in ipomsets, this approach uses concsets for interfaces. The labeling functor assigns a canonical interval ipomset to every path, preserving only precedence and concurrency, while discarding the artificial linear order of concurrent events.
Gluing Composition: The semantics utilize the gluing composition of ipomsets to compose path labels, ensuring the result remains an interval ipomset.

C. Path Lifting and Symmetrization

The paper defines a symmetrization functor ( $S$ ) that maps any ordered HDA to a symmetric HDA.
It establishes that paths in the symmetric HDA ( $SX$ ) are "liftings" of paths in the original HDA ( $X$ ), involving permutations of event labels at each step.
Crucially, it proves that the ST-trace (start/termination trace) is invariant under symmetrization, while the ipomset label is preserved up to isomorphism.

3. Key Contributions

Categorical Isomorphism of HDAs:
The paper proves that the category of HDAs over the order-free base $\Xi$ is isomorphic to the category of symmetric HDAs (based on $\Xi_g$ ). This formally justifies the use of order-free semantics for the entire class of HDAs, leveraging Kahl's Symmetrization Theorem (that every HDA is hhp-bisimilar to its symmetric expansion).
Order-Free Path Semantics:
A new labeling functor is introduced that maps HDA paths to interval ipomsets defined over concsets. This eliminates representational artifacts, ensuring that isomorphic ipomsets correspond to observationally equivalent executions (e.g., $(a \parallel b) \cong (b \parallel a)$ ).
Trace Correspondence:
The paper establishes a rigorous bridge between ST-traces and ipomset labels.
- It proves that if two paths have the same ST-trace, their ipomset labels are isomorphic.
- Conversely, if two paths have isomorphic ipomset labels, there exist congruent paths (paths related by adjacency swaps) that share the same ST-trace. This resolves the ambiguity between trace-based and pomset-based semantics.
Unified Bisimulation Characterization:
The paper reformulates ST-bisimulation and hereditary history-preserving (hhp) bisimulation entirely in terms of ipomset isomorphism.
- Two HDAs are hhp-bisimilar if and only if there exists a relation between their paths that preserves initial states, respects path extension, and maps paths to isomorphic ipomsets.

4. Results

Resolution of Logical Asymmetry: By removing the artificial event order, the proposed semantics restores symmetry. Modal logics derived from this framework will no longer distinguish between $a \parallel b$ and $b \parallel a$ unless there is a genuine causal difference.
Canonical Open Maps Framework: The order-free semantics provides the necessary path-category structure to canonically apply the Open Maps framework. This allows for the systematic derivation of modal logics that correctly characterize hhp-bisimulation without the artifacts of ordered representations.
Unification of Models: The results bridge the gap between HDAs and other concurrency models (like Petri nets and event structures) that do not rely on a global event order, facilitating better integration and comparison.

5. Significance

This paper provides a foundational correction to the theory of Higher-Dimensional Automata. By identifying the "event order" in standard HDAs as a representational artifact rather than a semantic necessity, the author:

Simplifies the Theory: It unifies the treatment of ordered and symmetric HDAs, showing they are categorically equivalent when viewed through the lens of hhp-bisimulation.
Enables Robust Logic: It removes the barriers preventing the application of powerful categorical tools (Open Maps) to HDAs, paving the way for more accurate and symmetric temporal and modal logics.
Clarifies Semantics: It resolves long-standing ambiguities in the literature regarding the relationship between ST-traces and pomset semantics, proving that ipomset isomorphism is the correct semantic equivalence for true concurrency.

In summary, the paper argues that to truly model concurrency, one must "forget" the arbitrary linear ordering of events, replacing it with a geometric, order-free structure based on interval ipomsets and symmetric presheaves.