J Ér

Émie Chalopin
email: jeremie.chalopin@lif.univ-mrs.fr

Victor Chepoi
email: victor.chepoi@lif.univ-mrs.fr

A COUNTEREXAMPLE TO THIAGARAJAN'S CONJECTURE ON REGULAR EVENT STRUCTURES 1

Keywords: Regular event structures, event domains, trace labelings, median graphs, CAT(0) cube complexes, universal covers, virtually special cube complexes, aperiodic tilings

 that domains of regular event structures with bounded -cliques are recognizable by finite trace automata. Event structures, trace automata, and Petri nets are fundamental models in concurrency theory. There exist nice interpretations of these structures as combinatorial and geometric objects and both conjectures can be reformulated in this framework. Namely, from a graph theoretical point of view, the domains of prime event structures correspond exactly to median graphs; from a geometric point of view, these domains are in bijection with CAT(0) cube complexes.

.

 Wise (2008, 2012) from geometric group theory, we prove that Thiagarajan's conjecture is true for regular event structures whose domains occur as principal filters of hyperbolic CAT(0) cube complexes which are universal covers of finite nonpositively curved cube complexes.

Introduction

Event structures, introduced by Nielsen, Plotkin, and Winskel [START_REF] Nielsen | Petri nets, event structures and domains, part I[END_REF][START_REF] Winskel | Events in computation[END_REF][START_REF] Winskel | Models for concurrency[END_REF], are a widely recognized abstract model of concurrent computation. An event structure (or more precisely, a prime event structure or an event structure with binary conflict) is a partially ordered set of the occurrences of actions, called events, together with a conflict relation. The partial order captures the causal dependency of events. The conflict relation models incompatibility of events so that two events that are in conflict cannot simultaneously occur in any state of the computation. Consequently, two events that are neither ordered nor in conflict may occur concurrently. More formally, an event structure is a triple E = (E, ≤, #), consisting of a set E of events, and two binary relations ≤ and #, the causal dependency ≤ and the conflict relation # with the requirement that the conflict is inherited by the partial order ≤. The pairs of events not in ≤ ∪ ≥ ∪ # define the concurrency relation . The domain of an event structure consists of all computation states, called configurations. Each computation state is a subset of events subject to the constraints that no two conflicting events can occur together in the same computation and if an event occurred in a computation then all events on which it causally depends have occurred too. Therefore, the domain of an event structure E is the set D(E) of all finite configurations ordered by inclusion. An event e is said to be enabled by a configuration c if e / ∈ c and c ∪ {e} is a configuration. The degree of an event structure E is the maximum number of events enabled by a configuration of E. The future (or the principal filter, or the residual) of a configuration c is the set of all finite configurations c containing c.

Among other things, the importance of event structures stems from the fact that several fundamental models of concurrent computation lead to event structures. Nielsen, Plotkin, and Winskel [START_REF] Nielsen | Petri nets, event structures and domains, part I[END_REF] proved that every 1-safe Petri net N unfolds into an event structure E N . Later results of [START_REF] Nielsen | Transition systems, event structures and unfoldings[END_REF] and [START_REF] Winskel | Models for concurrency[END_REF] show in fact that 1-safe Petri nets and event structures represent each other in a strong sense. In the same vein, Stark [START_REF] Stark | Connections between a concrete and an abstract model of concurrent systems[END_REF] established that the domains of configurations of trace automata are exactly the conflict event domains; a presentation of domains of event structures as trace monoids (Mazurkiewicz traces) or as asynchronous transition systems was given in [START_REF] Rozoy | Event structures and trace monoids[END_REF] and [START_REF] Bednarczyk | Categories of Asynchronous Systems[END_REF], respectively. In both cases, the events of the resulting event structure are labeled (in the case of trace monoids and trace automata-by the letters of a possibly infinite trace alphabet M = (Σ, I)) in a such a way that any two events enabled by the same configuration are labeled differently (such a labeling is usually called a nice labeling).

To deal with finite 1-safe Petri nets, Thiagarajan [START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF] introduced the notions of regular event structure and regular trace event structure. A regular event structure E is an event structure with a finite number of isomorphism types of futures of configurations and finite degree. A regular trace event structure is an event structure E whose events can be nicely labeled by the letters of a finite trace alphabet M = (Σ, I) in a such a way that the labels of any two concurrent events define a pair of I and there exists only a finite number of isomorphism types of labeled futures of configurations. These definitions were motivated by the fact that the event structures E N arising from finite 1-safe Petri nets N are regular: Thiagarajan [START_REF] Thiagarajan | Regular trace event structures[END_REF] proved that event structures of finite 1-safe Petri nets correspond to regular trace event structures. This lead Thiagarajan to formulate the following conjecture: Conjecture 1.1 ( [START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF]). A prime event structure E is isomorphic to the event structure E N arising from a finite 1-safe Petri net N if and only if E is regular.

Badouel, Darondeau, and Raoult [START_REF] Badouel | Context-free event domains are recognizable[END_REF] formulated two similar conjectures about conflict event domain that are recognizable by finite trace automata. The first one is equivalent to Conjecture 1.1, while the second one is formulated in a more general setting with an extra condition. We formulate their second conjecture in the particular case of event structures: Conjecture 1.2 ( [START_REF] Badouel | Context-free event domains are recognizable[END_REF]). A conflict event domain is recognizable if and only if the event structure E is regular and has bounded -cliques.

In view of previous results, to establish Conjecture 1.1, it is necessary for a regular event structure E to have a regular nice labeling with letters from some trace alphabet (Σ, I). Nielsen and Thiagarajan [36] proved in a technically involved but very nice combinatorial way that all regular conflict-free event structures satisfy Conjecture 1.1. In a equally difficult and technical proof, Badouel et al. [START_REF] Badouel | Context-free event domains are recognizable[END_REF] proved that their conjectures hold for context-free event domains, i.e., for domains whose underlying graph is a context-free graph sensu Müller and Schupp [START_REF] Muller | The theory of ends, pushdown automata, and second-order logic[END_REF]. In this paper, we present a counterexample to Thiagarajan's Conjecture based on a more geometric and combinatorial view on event structures. We show that our example also provides a counterexample to Conjecture 1.2 of Badouel et al.

We use the striking bijections between the domains of event structures, median graphs, and CAT(0) cube complexes. Median graphs have many nice properties and admit numerous characterizations. They have been investigated in several contexts for more than half a century, and play a central role in metric graph theory; for more detailed information, the interested reader can consult the surveys [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Bandelt | Median algebras[END_REF]. On the other hand, CAT(0) cube complexes are central objects in geometric group theory [START_REF] Sageev | Ends of group pairs and non-positively curved cube complexes[END_REF][START_REF] Sageev | CAT(0) cube complexes and groups[END_REF][START_REF] Wise | From Riches to Raags: 3-manifolds, Right-angled Artin Groups, and Cubical Geometry[END_REF]. They have been characterized in a nice combinatorial way by Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] as simply connected cube complexes in which the links of 0-cubes are simplicial flag complexes. It was proven in [START_REF] Chepoi | Graphs of some CAT(0) complexes[END_REF][START_REF] Roller | Poc sets, median algebras and group actions[END_REF] that 1-skeleta of CAT(0) cube complexes are exactly the median graphs. Barthélemy and Constantin [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF] proved that the Hasse diagrams of domains of event structures are median graphs and every pointed median graph is the domain of an event structure. The bijection between pointed median graphs and event domains established in [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF] can be viewed as the classical characterization of prime event domains as prime algebraic coherent partial orders provided by Nielsen, Plotkin, and Winskel [START_REF] Nielsen | Petri nets, event structures and domains, part I[END_REF]. More recently, this result was rediscovered in [START_REF] Ardila | Geodesics in CAT(0) cubical complexes[END_REF] in the language of CAT(0) cube complexes. Via these bijections, the events of an event structure E correspond to the parallelism classes of edges of the domain D(E) viewed as a median graph. We recall these bijections in Section 3.

Since in our paper we deal only with regular event structures, we need to be able to construct regular event domains from CAT(0) cube complexes. By Gromov's characterization, CAT(0) cube complexes are exactly the universal covers of cube complexes satisfying the link condition, i.e., of nonpositively curved cube (NPC) complexes. Of particular importance for us are the CAT(0) cube complexes arising as universal covers of finite NPC complexes. In Section 4, we adapt the universal cover construction to directed NPC complexes (Y, o) and show that every principal filter of the directed universal cover ( Y , o) is the domain of an event structure. Furthermore, we show that if the NPC complex Y is finite, then this event structure is regular. Motivated by this result, we call an event structure strongly regular if its domain is the principal filter of the directed universal cover ( Y , o) of a finite directed NPC complex (Y, o).

Our counterexample to Conjectures 1.1 and 1.2 is a strongly regular event structure derived from Wise's [START_REF] Wise | Non-positively curved squared complexes, aperiodic tilings, and non-residually finite groups[END_REF][START_REF] Wise | Complete square complexes[END_REF] nonpositively curved square complex X obtained from a tile set with six tiles. This counterexample is described in Section 6. In Section 7 we also prove that other counterexamples to Thiagarajan's conjecture arise in a similar way from any aperiodic 4-deterministic tile set, such as the ones constructed by Kari and Papasoglu [START_REF] Kari | Deterministic aperiodic tile sets[END_REF] and Lukkarila [START_REF] Lukkarila | The 4-way deterministic tiling problem is undecidable[END_REF].

On the positive side, in Section 5 we prove that Thiagarajan's conjecture is true for event structures whose domains arise as principal filters of universal covers of finite special cube complexes. Haglund and Wise [START_REF] Haglund | Special cube complexes[END_REF][START_REF] Haglund | A combination theorem for special cube complexes[END_REF] detected pathologies which may occur in NPC complexes: self-intersecting hyperplanes, one-sided hyperplanes, directly self-osculating hyperplanes, and pairs of hyperplanes, which both intersect and osculate. They called the NPC complexes without such pathologies special. The main motivation for introducing and studying special cube complexes was the profound idea of Wise that the famous virtual Haken conjecture for hyperbolic 3-manifolds can be reduced to solving problems about special cube complexes. In a breakthrough result, Agol [START_REF] Agol | The conjecture[END_REF][START_REF] Agol | Virtual properties of 3-manifolds[END_REF] completed this program and solved the virtual Haken conjecture using the deep theory of special cube complexes developed by Haglund and Wise [START_REF] Haglund | Special cube complexes[END_REF][START_REF] Haglund | A combination theorem for special cube complexes[END_REF]. The main ingredient in this proof is Agol's theorem that finite NPC complexes whose universal covers are hyperbolic are virtually special (i.e., they admit finite covers which are special cube complexes). Using this result of Agol, we can specify our previous result and show that Thiagarajan's conjecture is true for strongly regular event structures whose domains occur as principal filters of hyperbolic CAT(0) cube complexes that are universal covers of finite directed NPC complexes. Since context-free domains are hyperbolic, this result can be viewed in some sense as a partial generalization of the result of Badouel et al. [START_REF] Badouel | Context-free event domains are recognizable[END_REF].

To conclude this introductory section, we briefly describe the construction of our counterexample to Thiagarajan's conjecture. It is based on Wise's [START_REF] Wise | Non-positively curved squared complexes, aperiodic tilings, and non-residually finite groups[END_REF][START_REF] Wise | Complete square complexes[END_REF] directed nonpositively curved square complex X with one vertex and six squares, whose edges are colored in five colors, and whose colored universal cover X contains a particular directed plane with an aperiodic tiling. The edges of X are partitioned into two classes (horizontal and vertical edges) and opposite edges of squares are oriented in the same way. As a result, X is a directed CAT(0) square complex whose edges are colored by the colors of their images in X and are directed in such a way that all edges dual to the same hyperplane are oriented in the same way. With respect to this orientation, all vertices of X are equivalent up to automorphism. We modify the complex X by taking its first barycentric subdivision and by adding to the middles of the edges of X directed paths of five different lengths (tips) in order to encode the colors of the edges of X (and X) and to obtain a directed nonpositively curved square complex W . The universal cover W of W is a directed (but no longer colored) CAT(0) square complex. W can be viewed as the first barycentric subdivision of the support X of X in which to each vertex arising from a middle of an edge of X a tip encoding the color of the original edge is added. Since W is the universal cover of a finite complex W , W has a finite number of equivalence classes of vertices up to automorphism. From W we derive a domain of a regular event structure W v by considering the future of an arbitrary vertex v of X. Using the fact that X contains a particular directed plane with an aperiodic tiling, we prove that W v does not admit a regular nice labeling, thus W v is the domain of a regular event structure not having a regular trace labeling.

Event structures

2.1. Event structures and domains. An event structure is a triple E = (E, ≤, #), where

• E is a set of events,

• ≤⊆ E × E is a partial order of causal dependency,

• # ⊆ E × E is a binary, irreflexive, symmetric relation of conflict,
• ↓ e := {e ∈ E : e ≤ e} is finite for any e ∈ E,

• e#e and e ≤ e imply e#e . What we call here an event structure is usually called a coherent event structure, an event structure with a binary conflict, or a prime event structure. Two events e , e are concurrent (notation e e ) if they are order-incomparable and they are not in conflict. The conflict e #e between two elements e and e is said to be minimal (notation e # µ e ) if there is no event e = e , e such that either e ≤ e and e#e or e ≤ e and e#e . We say that e is an immediate predecessor of e (notation e e ) if and only if e ≤ e , e = e , and for every e if e ≤ e ≤ e , then e = e or e = e .

Given two event structures

E 1 = (E 1 , ≤ 1 , # 1 ) and E 2 = (E 2 , ≤ 2 , # 2 ), a map f : E 1 → E 2 is an isomorphism if f is a bijection such that e ≤ 1 e iff f (e) ≤ 2 f (e ) and e# 1 e iff f (e)# 2 f (e )
for every e, e ∈ E 1 . If such an isomorphism exists, then E 1 and E 2 are said to be isomorphic; notation

E 1 ≡ E 2 .
A configuration of an event structure E = (E, ≤, #) is any finite subset c ⊂ E of events which is conflict-free (e, e ∈ c implies that e, e are not in conflict) and downward-closed (e ∈ c and e ≤ e implies that e ∈ c) [START_REF] Winskel | Models for concurrency[END_REF]. Notice that ∅ is always a configuration and that ↓ e and ↓ e \ {e} are configurations for any e ∈ E. The domain of an event structure is the set For an event structure E = (E, ≤, #), let be the least irreflexive and symmetric relation on the set of events E such that e 1 e 2 if (1) e 1 e 2 , or (2) e 1 # µ e 2 , or (3) there exists an event e 3 that is co-initial with e 1 and e 2 at two different configurations such that e 1 e 3 and e 2 # µ e 3 (see Figure 1 for examples). (If e 1 e 2 and this comes from condition (3), then we write e 1 (3) e 2 .) A -clique is any complete subgraph of the graph whose vertices are the events and whose edges are the pairs of events e 1 e 2 such that e 1 e 2 .

D := D(E)
A labeled event structure E λ = (E, λ) is defined by an underlying event structure E = (E, ≤, #) and a labeling λ that is a map from E to some alphabet Σ. Two labeled event structures

E λ 1 1 = (E 1 , λ 1 ) and E λ 1 2 = (E 2 , λ 2 ) are isomorphic (notation E λ 1 1 ≡ E λ 2
2 ) if there exists an isomorphism f between the underlying event structures E 1 and E 2 such that λ 2 (f (e 1 )) = λ 1 (e 1 ) for every e 1 ∈ E 1 .

A labeling λ : E → Σ of an event structure E defines naturally a labeling of the directed edges of the Hasse diagram of its domain D(E) that we also denote by λ. A labeling λ : E → Σ of an event structure E is called a nice labeling if any two events that are co-initial have different labels [START_REF] Rozoy | Event structures and trace monoids[END_REF]. A nice labeling of E can be reformulated as a labeling of the directed edges of the Hasse diagram of its domain D(E)) subject to the following local conditions: In the following, we use interchangeably the labeling of an event structure and the labeling of the edges of its domain.

Regular event structures.

In this subsection, we recall the definitions of regular event structures, regular trace event structures, and regular nice labelings of event structures. We closely follow the definitions and notations of [36,[START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF]. Let E = (E, ≤, #) be an event structure. Let c be a configuration of E. Set #(c) = {e : ∃e ∈ c, e#e }. The event structure rooted at c is defined to be the triple E\c = (E , ≤ , # ), where For an event structure E = (E, ≤, #), define the equivalence relation R E on its configurations in the following way: for two configurations c and c set cR E c if and only if E\c ≡ E\c . The index of an event structure E is the number of equivalence classes of R E , i.e., the number of isomorphism types of futures of configurations of E. The event structure E is regular [36, [START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF] if E has finite index and finite degree. Now, let E λ = (E, λ) be a labeled event structure. For any configuration c of E, if we restrict λ to E\c, then we obtain a labeled event structure (E\c, λ) denoted by E λ \c. Analogously, define the equivalence relation R E λ on its configurations by setting cR E λ c if and only if E λ \c ≡ E λ \c . The index of E λ is the number of equivalence classes of R E λ . We say that an event structure E admits a regular nice labeling if there exists a nice labeling λ of E with a finite alphabet Σ such that E λ has finite index.

E = E \ (c ∪ #(c)), ≤ is ≤ restricted to E × E ,
We continue by recalling the definition of regular trace event structures from [START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF]. A (Mazurkiewicz) trace alphabet is a pair M = (Σ, I), where Σ is a finite non-empty alphabet set and I ⊂ Σ × Σ is an irreflexive and symmetric relation called the independence relation. We call λ a trace labeling of E with the trace alphabet (Σ, I). The conditions (LES2) and (LES3) on the labeling function ensures that the concurrency relation of E respects the independence relation I of M . In particular, since I is irreflexive, from (LES3) it follows that any two concurrent events are labeled differently. Since by (LES1) two events in minimal conflict are also labeled differently, this implies that λ is a finite nice labeling of E.

An M -labeled event structure E λ = (E, λ) is regular if E λ has finite index. Finally, an event structure E is called a regular trace event structure [START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF] iff there exists a trace alphabet M = (Σ, I) and a regular M -labeled event structure E λ such that E is isomorphic to the underlying event structure of E λ . From the definition immediately follows that every regular trace event structure is also a regular event structure. It turns out that the converse is equivalent to Conjecture 1.1. Namely, [START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF] establishes the following equivalence (this result dispenses us from giving a formal definition of 1-safe Petri nets; the interested readers can find it in the papers [36,[START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF]): Theorem 1]). E is a regular trace event structure if and only if there exists a finite 1-safe Petri net N such that E and E N are isomorphic.

Theorem 2.1 ([44,
In view of this theorem, Conjecture 1.1 is equivalent to the following conjecture: Conjecture 2.2. E is a regular event structure if and only if E is a regular trace event structure.

Badouel et al. [START_REF] Badouel | Context-free event domains are recognizable[END_REF] considered recognizable conflict event domains that are more general than the domains of event structures we consider in this paper. Since the domain of an event structure E is recognizable if and only if E is a regular trace event structure (see [START_REF] Morin | Concurrent automata vs. asynchronous systems[END_REF]Section 5]), Conjecture 1.2 can be reformulated as follows:

Conjecture 2.3. E is a regular event structure iff E is a regular trace event structure and E has bounded -cliques.

Since any regular trace labeling is a regular nice labeling, any regular event structure E not admitting a regular nice labeling is a counterexample to Conjecture 2.2 (and thus to Conjecture 1.1). If, additionally, E has bounded -cliques, E is also a counterexample to Conjecture 2.3 (and thus to Conjecture 1.2).

Domains, median graphs, and CAT(0) cube complexes

In this section, we recall the bijections between domains of event structures and median graphs/CAT(0) cube complexes established in [START_REF] Ardila | Geodesics in CAT(0) cubical complexes[END_REF] and [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF], and between median graphs and 1-skeleta of CAT(0) cube complexes established in [START_REF] Chepoi | Graphs of some CAT(0) complexes[END_REF] and [START_REF] Roller | Poc sets, median algebras and group actions[END_REF].

3.1. Median graphs. Let G = (V, E) be a simple, connected, not necessarily finite graph. The distance d G (u, v) between two vertices u and v is the length of a shortest (u, v)-path, and the interval I(u, v) between u and v consists of all vertices on shortest (u, v)-paths, that is, of all vertices (metrically) between u and v:

I(u, v) := {x ∈ V : d G (u, x) + d G (x, v) = d G (u, v)}.
An induced subgraph of G (or the corresponding vertex set) is called convex if it includes the interval of G between any of its vertices. A graph G = (V, E) is isometrically embeddable into a graph H = (W, F ) if there exists a mapping ϕ :

V → W such that d H (ϕ(u), ϕ(v)) = d G (u, v) for all vertices u, v ∈ V .
A graph G is called median if the interval intersection I(x, y)∩I(y, z)∩I(z, x) is a singleton for each triplet x, y, z of vertices. Median graphs are bipartite. Basic examples of median graphs are trees, hypercubes, rectangular grids, and Hasse diagrams of distributive lattices and of median semilattices [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF]. With any vertex v of a median graph G = (V, E) is associated a canonical partial order ≤ v defined by setting x ≤ v y if and only if x ∈ I(v, y); v is called the basepoint of ≤ v . Since G is bipartite, the Hasse diagram G v of the partial order (V, ≤ v ) is the graph G in which any edge xy is directed from x to y if and only if the inequality d G (x, v) < d G (y, v) holds. We call G v a pointed median graph. There is a close relationship between pointed median graphs and median semilattices. A median semilattice is a meet semilattice (P, ≤) such that (i) for every x, the principal ideal ↓ x = {p ∈ P : p ≤ x} is a distributive lattice, and (ii) any three elements have a least upper bound in P whenever each pair of them does.

Theorem 3.1 ([4]

). The Hasse diagram of any median semilattice is a median graph. Conversely, every median graph defines a median semilattice with respect to any canonical order ≤ v .

Median graphs can be obtained from hypercubes by amalgams and median graphs are themselves isometric subgraphs of hypercubes [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF][START_REF] Mulder | The Interval Function of a Graph[END_REF]. The canonical isometric embedding of a median graph G into a (smallest) hypercube can be determined by the so called Djoković-Winkler ("parallelism") relation Θ on the edges of G [START_REF] Djoković | Distance-preserving subgraphs of hypercubes[END_REF][START_REF] Winkler | Isometric embedding in products of complete graphs[END_REF]. For median graphs, the equivalence relation Θ can be defined as follows. First say that two edges uv and xy are in relation Θ if they are opposite edges of a 4-cycle uvxy in G. Then let Θ be the reflexive and transitive closure of Θ . Any equivalence class of Θ constitutes a cutset of the median graph G, which determines one factor of the canonical hypercube [START_REF] Mulder | The Interval Function of a Graph[END_REF]. The cutset (equivalence class) Θ(xy) containing an edge xy defines a convex split {W (x, y), W (y, x)} of G [START_REF] Mulder | The Interval Function of a Graph[END_REF], where W (x, y) = {z ∈ V : d G (z, x) < d G (z, y)} and W (y, x) = V \ W (x, y) (we call the complementary convex sets W (x, y) and W (y, x) halfspaces). Conversely, for every convex split of a median graph G there exists at least one edge xy such that {W (x, y), W (y, x)} is the given split. We denote by {Θ i : i ∈ I} the equivalence classes of the relation Θ (in [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF], they were called parallelism classes). For an equivalence class Θ i , i ∈ I, we denote by {A i , B i } the associated convex split. We say that Θ i separates the vertices x and y if x ∈ A i , y ∈ B i or x ∈ B i , y ∈ A i . The isometric embedding ϕ of G into a hypercube is obtained by taking a basepoint v, setting ϕ(v) = ∅ and for any other vertex u, letting ϕ(u) be all parallelism classes of Θ which separate u from v.

We conclude this subsection with the following simple but useful local characterization of convex sets of median graphs (which holds for much more general classes of graphs): Lemma 3.2. Let S be a connected subgraph of a median graph G. Then S is a convex subgraph if and only if S is locally-convex, i.e., I(x, y) ⊆ S for any two vertices x, y of S having a common neighbor in S.

Nonpositively curved cube complexes.

A 0-cube is a single point. A 1-cube is an isometric copy of the segment [-1, 1] and has a cell structure consisting of 0-cells {±1} and a single 1-cell. An n-cube is an isometric copy of [-1, 1] n , and has the product structure, so that each closed cell of [-1, 1] n is obtained by restricting some of the coordinates to +1 and some to -1. A cube complex is obtained from a collection of cubes of various dimensions by isometrically identifying certain subcubes. The dimension of a cube complex X is the largest value of d for which X contains a d-cube. A square complex is a cube complex of dimension 2. The 0-cubes and the 1-cubes of a cube complex X are called vertices and edges of X and define the graph X (1) , the 1-skeleton of X. We denote the vertices of X (1) by V (X) and the edges of X (1) by E(X). For i ∈ N, we denote by X (i) the i-skeleton of X, i.e., the cube complex consisting of all j-dimensional cubes of X, where j ≤ i. A square complex X is a combinatorial 2-complex whose 2-cells are attached by closed combinatorial paths of length 4. Thus, one can consider each 2-cell as a square attached to the 1-skeleton X (1) of X. The star St(v, X) of a vertex v of X is the subcomplex spanned by all cubes containing v. The link of a vertex x ∈ X is the simplicial complex Link(x) with a (d -1)-simplex for each d-cube containing x, with simplices attached according to the attachments of the corresponding cubes. The link Link(x) is said to be a flag (simplicial) complex if each (d + 1)-clique in Link(x) spans an d-simplex. This flagness condition of Link(x) can be restated as follows: whenever three (k + 2)-cubes of X share a common k-cube containing x and pairwise share common (k + 1)-cubes, then they are contained in a (k + 3)-cube of X. A cube complex X is called simply connected if it is connected and if every continuous mapping of the 1-dimensional sphere S 1 into X can be extended to a continuous mapping of the disk D 2 with boundary S 1 into X. Note that X is connected iff G(X) = X (1) is connected, and X is simply connected iff X (2) is simply connected. Equivalently, a cube complex X is simply connected if X is connected and every cycle C of its 1-skeleton is null-homotopic, i.e., it can be contracted to a single point by elementary homotopies.

Given two cube complexes X and Y , a covering (map) is a surjection ϕ : Y → X mapping cubes to cubes and such that ϕ

| St(v,Y ) : St(v, Y ) → St(ϕ(v), X) is an isomorphism for every vertex v in Y .
The space Y is then called a covering space of X. A universal cover of X is a simply connected covering space; it always exists and it is unique up to isomorphism [START_REF] Hatcher | Algebraic Topology[END_REF]Sections 1.3 and 4.1]. The universal cover of a complex X will be denoted by X. In particular, if X is simply connected, then its universal cover X is X itself.

An important class of cube complexes studied in geometric group theory and combinatorics is the class of nonpositively curved and CAT(0) cube complexes. We continue by recalling the definition of CAT(0) spaces. A geodesic triangle ∆ = ∆(x 1 , x 2 , x 3 ) in a geodesic metric space (X, d) consists of three points in X (the vertices of ∆) and a geodesic between each pair of vertices (the sides of ∆). A comparison triangle for ∆(x 1 , x 2 , x 3 ) is a triangle ∆(x 1 , x 2 , x 3 ) in the Euclidean plane E 2 such that d E 2 (x i , x j ) = d(x i , x j ) for i, j ∈ {1, 2, 3}. A geodesic metric space (X, d) is defined to be a CAT(0) space [START_REF] Gromov | Hyperbolic groups[END_REF] if all geodesic triangles ∆(x 1 , x 2 , x 3 ) of X satisfy the comparison axiom of Cartan-Alexandrov-Toponogov: If y is a point on the side of ∆(x 1 , x 2 , x 3 ) with vertices x 1 and x 2 and y is the unique point on the line segment

[x 1 , x 2 ] of the comparison triangle ∆(x 1 , x 2 , x 3 ) such that d E 2 (x i , y ) = d(x i , y) for i = 1, 2, then d(x 3 , y) ≤ d E 2 (x 3 , y ). A geodesic metric space (X, d) is nonpositively curved if it is locally CAT(0), i.e.
, any point has a neighborhood inside which the CAT(0) inequality holds. CAT(0) spaces can be characterized in several different natural ways and have many strong properties, see for example [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF]. In particular, a geodesic metric space (X, d) is CAT(0) if and only if (X, d) is simply connected and is nonpositively curved. Gromov [START_REF] Gromov | Hyperbolic groups[END_REF] gave a beautiful combinatorial characterization of CAT(0) cube complexes, which can be also taken as their definition:

Theorem 3.3 ([ 22
]). A cube complex X endowed with the 2 -metric is CAT(0) if and only if X is simply connected and the links of all vertices of X are flag complexes. If Y is a cube complex in which the links of all vertices are flag complexes, then the universal cover Y of Y is a CAT(0) cube complex.

In view of the second assertion of Theorem 3.3, the cube complexes in which the links of vertices are flag complexes are called nonpositively curved cube complexes or shortly NPC complexes. As a corollary of Gromov's result, for any NPC complex X, its universal cover X is CAT(0).

A square complex X is a V H-complex (vertical-horizontal complex) if the 1-cells (edges) of X are partitioned into two sets V and H called vertical and horizontal edges respectively, and the edges in each square alternate between edges in V and H. Notice that if X is a V H-complex, then X satisfies the Gromov's nonpositive curvature condition since no three squares may pairwise intersect on three edges with a common vertex, thus V H-complexes are particular NPC square complexes. A V H-complex X is a complete square complex (CSC) [START_REF] Wise | Complete square complexes[END_REF] if any vertical edge and any horizontal edge incident to a common vertex belong to a common square of X. By [51, Theorem 3.8], if X is a complete square complex, then the universal cover X of X is isomorphic to the Cartesian product of two trees. By a plane Π in X we will mean a convex subcomplex of X isometric to R 2 tiled by the grid Z 2 into unit squares.

We continue with the bijection between CAT(0) cube complexes and median graphs: [START_REF] Chepoi | Graphs of some CAT(0) complexes[END_REF][START_REF] Roller | Poc sets, median algebras and group actions[END_REF]). Median graphs are exactly the 1-skeleta of CAT(0) cube complexes.

Theorem 3.4 ([
The proof of Theorem 3.4 presented in [START_REF] Chepoi | Graphs of some CAT(0) complexes[END_REF] is based on the following local-to-global characterization of median graphs: Theorem 3.5 ([17]). A graph G is a median graph if and only if its cube complex is simply connected and G satisfies the 3-cube condition: if three squares of G pairwise intersect in an edge and all three intersect in a vertex, then they belong to a 3-cube.

A midcube of the d-cube c, with d ≥ 1, is the isometric subspace obtained by restricting exactly one of the coordinates of d to 0. Note that a midcube is a (d -1)-cube. The midcubes a and b of X are adjacent if they have a common face, and a hyperplane H of X is a subspace that is a maximal connected union of midcubes such that, if a, b ⊂ H are midcubes, either a and b are disjoint or they are adjacent. Equivalently, a hyperplane H is a maximal connected union of midcubes such that, for each cube c, either H ∩ c = ∅ or H ∩ c is a single midcube of c.

Theorem 3.6 ( [40]

). Each hyperplane H of a CAT(0) cube complex X is a CAT(0) cube complex of dimension at most dim X -1 and X \ H consists of exactly two components, called halfspaces.

A 1-cube e (an edge) is dual to the hyperplane H if the 0-cubes of e lie in distinct halfspaces of X \ H, i.e., if the midpoint of e is in a midcube contained in H. The relation "dual to the same hyperplane" is an equivalence relation on the set of edges of X; denote this relation by Θ and denote by Θ(H) the equivalence class consisting of 1-cubes dual to the hyperplane H (Θ is precisely the parallelism relation on the edges of the median graph X (1) ).

3.3. Domains versus median graphs/CAT(0) cube complexes. Theorems 2.2 and 2.3 of Barthélemy and Constantin [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF] establish the following bijection between event structures and pointed median graphs (in [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF], event structures are called sites): The first part of this theorem first establishes that each event domain is a median semilattice (in fact, the conditions (i) and (ii) of a median semilattice are often taken as the definition of a domain, see for example, [START_REF] Badouel | Context-free event domains are recognizable[END_REF][START_REF] Winskel | An introduction to event structures[END_REF]) and follows from Avann's Theorem 3.1. The bijection between domains of event structures and median semilattices is equivalent to the bijection between domains of event structures and prime algebraic coherent partial orders established in [START_REF] Nielsen | Petri nets, event structures and domains, part I[END_REF]. With the help of Theorem 3.5, we can provide an alternative proof of the first part of Theorem 3.7, which we hope can be of independent interest. Since we will use it further, we also recall the construction of an event structure from a pointed median graph presented in [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF].

Proof of Theorem 3.7. To prove that the square complex of an event domain D := D(E) is simply connected one has to show that any cycle σ of the Hasse diagram of D is 0-homotopic. We proceed by lexicographic induction on the pair (n 1 (σ), n 2 (σ)), where n 1 (σ) is the maximum cardinality of a configuration of σ and n 2 (σ) is the number of configurations (vertices) of σ of size n 1 (σ). Let c be a configuration of σ of maximum size n 1 (σ). Then the neighbors c , c of c in σ have cardinality n 1 (σ) -1, say c = c \ {e } and c = c \ {e }. If e = e , then let σ be the obtained from σ by removing c. If e = e , then the set c 0 := c \ {e , e } is conflict-free and downward closed, thus c 0 is a configuration. As a result, the configurations c, c , c 0 , c define a square. In this case, let σ be the cycle obtained obtained from σ by replacing c by c 0 . Note that there is an elementary homotopy from σ to σ via the square cc c 0 c . In both cases, if

n 2 (σ) > 1, then n 1 (σ ) = n 1 (σ) and n 2 (σ ) = n 2 (σ) -1. If n 2 (σ) = 1, then n 1 (σ ) = n 1 (σ) -1.
In both cases, by induction hypothesis we may assume that σ is 0-homotopic. Since there exists an elementary homotopy from σ to σ in both cases, the cycle σ is also 0-homotopic. To show that the graph of D satisfies the 3-cube condition, one can see that there exist four possible embeddings of the three squares in D. In each of these cases one can directly conclude that the vertex v completing them to a 3-cube must be a configuration (see Figure 2). Indeed, in the first three cases, the set c(v) of events corresponding to this vertex is included in a configuration, thus it is conflict-free. It can be also easily seen that in all three cases c(v) is downward-closed, i.e., c(v) is a configuration. In the last case, c(v) = σ ∪ {e 1 , e 2 , e 3 }. Each pair of events of c(v) is contained in one of the configurations σ ∪ {e i , e j }, i, j ∈ {1, 2, 3}, i = j, whence c(v) is conflict-free. Pick any e ∈ c(v). If e ∈ σ, then ↓ e ⊂ σ. If e ∈ {e 1 , e 2 , e 3 }, say e = e 1 , then ↓ e ⊂ σ ∪ {e 1 }. In both cases we conclude that ↓ e ⊂ c(v), i.e., c(v) is downward-closed, whence c(v) is a configuration. Now, we recall how to define the event structure occurring in the second part of the theorem. Suppose that v is an arbitrary but fixed basepoint of a median graph G. For an equivalence class Θ i , i ∈ I, we denote by {A i , B i } the associated convex split, and suppose without loss of generality that v ∈ A i . Two equivalence classes Θ i and Θ j are said to be crossing if there exists a 4-cycle C of G with two opposite edges in Θ i and two other opposite edges in Θ j (Θ i and Since Θ i ∈ U and Θ j ≤ Θ i implies that Θ j also separates v from u, and thus Θ j belongs to U , we conclude that U is downward-closed. If Θ i #Θ j and Θ i ∈ U , then necessarily Θ i and v belong to a common halfspace defined by Θ j . Therefore Θ j does not separate u from v. This shows that U is conflict-free, i.e., U is a configuration of E v . Conversely, any configuration c of E v consists of exactly those Θ i that separate v from the vertex representing c. This concludes the proof of Theorem 3.7.

Rephrasing the construction of an event structure from a pointed median graph presented in the proof of Theorem 3.7, to each CAT(0) cube complex X and each vertex v of X one can associate an event structure E v such that the domain of E v is the 1-skeleton of X pointed at v. The events of E v are the hyperplanes of X. Hyperplanes H and H define concurrent events if and only if they cross, and H ≤ H if and only if H = H or H separates H from v. The events defined by H and H are in conflict if and only if H and H do not cross and neither separates the other from v.

Related work.

The link between event domains, median graphs, and CAT(0) cube complexes allows a more geometric and combinatorial approach to several questions on event structures (and to work only with CAT(0) cube complexes viewed as event domains). For example, this allowed [START_REF] Chepoi | Nice labeling problem for event structures: a counterexample[END_REF] to disprove the so-called nice labeling conjecture of Rozoy and Thiagarajan [START_REF] Rozoy | Event structures and trace monoids[END_REF] asserting that any event structure of finite degree admit a finite nice labeling. The topological dimension dim X of a CAT(0) cube complex X corresponds to the maximum number of pairwise concurrent events of E v and to the clique number of the intersection graph of hyperplanes of X. The degree deg(E v ) of the event structure E v is equal to the maximum out-degree of a vertex in the canonical order ≤ v of the 1-skeleton of X (and is equal to the clique number of a so-called pointed contact graph of hyperplanes of X [START_REF] Chepoi | Nice labeling problem for event structures: a counterexample[END_REF][START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF]). In particular, dim X ≤ deg(E v ). Notice also that the maximum degree of a vertex of X is upper bounded by deg

(E v ) + dim(X) ≤ 2 deg(E v )
and is equal to the clique number of the contact graph of hyperplanes of X (the intersection graph of the carriers of X) [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF][START_REF] Hagen | Weak hyperbolicity of cube complexes and quasi-arboreal groups[END_REF]. Using this terminology, a nice labeling of the event structure E v is equivalent to a coloring of the pointed contact graph of X. Using this combinatorial reformulation and the example of Burling [START_REF] Burling | On coloring problems of prototypes[END_REF] of families of axis-parallel boxes of R 3 with no three pairwise intersecting boxes and arbitrarily high chromatic number of the intersection graph, [START_REF] Chepoi | Nice labeling problem for event structures: a counterexample[END_REF] describes an example of a CAT(0) 4-dimensional cube complex with maximum degree 12 and infinite chromatic number of the pointed contact graph, thus providing a counterexample to the nice labeling conjecture of Rozoy and Thiagarajan [START_REF] Rozoy | Event structures and trace monoids[END_REF]. On the other hand, it is shown in [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF] that the nice labeling conjecture is true for event structures whose domains are 2-dimensional (i.e., event structures not containing three pairwise concurrent events).

Directed NPC complexes

Since we can define event structures from their domains, universal covers of NPC complexes represent a rich source of event structures. To obtain regular event structures, it is natural to consider universal covers of finite NPC complexes. Moreover, since domains of event structures are directed, it is natural to consider universal covers of NPC complexes whose edges are directed. However, the resulting directed universal covers are not in general domains of event structures. In particular, the domains corresponding to pointed median graphs given by Theorem 3.7 cannot be obtained in this way. In order to overcome this difficulty, we introduce directed median graphs and directed NPC complexes. Using these notions, one can naturally define regular event structures starting from finite directed NPC complexes.

of G. For a vertex v of G, let F o (v, G) = {x ∈ V : v ≺ o x}
be the principal filter of v in the partial order (V (G), ≺ o ). For any canonical basepoint order ≤ v of G, (G, ≤ v ) is a directed median graph. The converse is obviously not true: the 4-regular tree F 4 directed so that each vertex has two incoming and two outgoing arcs is a directed median graph which is not induced by a basepoint order. Proof. To (i): For each parallelism class Θ i , let A i , B i be the two convex subgraphs separated by Θ i and suppose without loss of generality that all edges of Θ i are directed from A i to B i . Let B be the intersection of all of the B i s containing the vertex v. We assert that

F o (v, G) coincides with B. F o (v, G) consists
P (v, u) = (v 0 = v, v 1 , . . . , v k-1 , v k = u) in G between v and u.
We claim that all edges of P (v, u) are directed from v to u, yielding u ∈ F o (v, G). Pick any edge v j v j+1 of P (v, u); suppose that v j v j+1 belongs to the parallelism class Θ i . By convexity of A i and B i , necessarily Θ i separates the vertices v and u. Since v, u ∈ B, this implies that v ∈ A i and u ∈ B i , i.e., the edge v j v j+1 is directed from v j to v j+1 . To (ii): First suppose that u , u ∈ F o (v, G) and u ≤ v u. This implies that u ∈ I(v, u). are directed from v to u. This implies that all the edges of the subpath of P (v, u) comprised between u and u are directed from u to u, yielding u ≺ o u. To prove the converse assertion, suppose by way of contradiction that F o (v, G) contains two vertices u , u such that u ≺ o u however u ≤ v u is not true, i.e., u / ∈ I(v, u). Among all vertices u for which this holds, suppose that u is chosen so that to minimize the length of a shortest directed path from u to u. Let w be a neighbor of u on a shortest directed path from u to u. Since u o w, w ∈ F o (v, G) and from the choice of u it follows that u ≤ v w, i.e., u ∈ I(v, w). Since G is bipartite, either w ∈ I(v, u) or u ∈ I(v, w) holds. If w ∈ I(v, u), since u ∈ I(v, w), we conclude that u ∈ I(v, u), a contradiction. Therefore u ∈ I(v, w). Since the edge wu is oriented from w to u and u lies on a shortest path from v to w, we obtain a contradiction with the fact that all the edges of such a shortest path must be directed from v to w. This contradiction establishes that the partial orders ≺ o and ≤ v coincide on F o (v, G).

Let P (v, u) = (v 0 = v, v 1 , . . . , v k-1 , v k = u)
To (iii)&(iv): By (i), the subgraph G of G induced by F o (v, G) is a median graph. By (ii), the partial order ≺ o coincides on G with the canonical basepoint order ≤ v . By Theorem 3.7, (V (G ), ≺ o ) is the domain of an event structure, establishing (iii). Finally, (iv) is an immediate consequence of (ii).

4.2.

Directed NPC cube complexes. A directed NPC complex is a pair (Y, o), where Y is a NPC complex and o is an orientation of the edges of Y in a such a way that the opposite edges of the same square of Y have the same direction. Such an orientation o of the edges of a NPC complex Y is called an admissible orientation of Y . Note that there exist NPC complexes that do not admit any admissible orientation: consider a Möbius band of squares, for example. An admissible orientation o of Y induces in a natural way an orientation o of the edges of its universal cover Y , so that ( Y , o) is a directed CAT(0) cube complex and ( Y (1) , o) is a directed median graph. A directed plane in a directed CAT(0) cube complex Y is a plane Π in Y such that for any vertex (i, j) of the grid Z 2 tiling Π, (i, j) is the source of the edges (i, j)(i, j + 1) and (i, j)(i + 1, j).

In the following, we need to consider directed colored NPC complexes and directed colored median graphs. A coloring ν of a directed NPC complex (Y, o) is an arbitrary map ν : E(Y ) → Υ where Υ is a set of colors. Note that a labeling is a coloring, but not the converse: labelings are precisely the colorings in which opposite edges of any square have the same color. In the following, we will denote a directed colored NPC complexes by bold letters like Y = (Y, o, ν). Sometimes, we need to forget the colors and the orientations of the edges of these complexes. For a complex Y, we denote by Y the complex obtained by forgetting the colors and the orientations of the edges of Y (Y is called the support of Y), and we denote by (Y, o) the directed complex obtained by forgetting the colors of Y. We also consider directed colored median graphs that will be the 1-skeletons of directed colored CAT(0) cube complexes. Again we will denote such directed colored median graphs by bold letters like G = (G, o, ν). Note that (uncolored) directed NPC complexes can be viewed as directed colored NPC complexes where all edges have the same color.

When dealing with directed colored NPC complexes, we consider only homomorphisms that preserve the colors and the directions of the edges. More precisely, Y = (Y , o , ν ) is a covering of Y = (Y, o, ν) via a covering map ϕ if Y is a covering of Y via ϕ and for any edge e ∈ E(Y ) directed from s to t, ν(ϕ(e)) = ν (e) and ϕ(e) is directed from ϕ(s) to ϕ(t). Since any coloring ν of a directed colored NPC complex Y leads to a coloring of its universal cover Y , one can consider the colored universal cover Y = ( Y , o, ν) of Y.

When we consider principal filters in directed colored median graphs G = (G, o, ν) (in particular, when G is the 1-skeleton of the universal cover Y of a directed colored NPC complex Y), we say that two filters are isomorphic if there is an isomorphism between them that preserves the directions and the colors of the edges.

We now formulate the crucial regularity property of directed colored median graphs ( Y (1) , o, ν) when (Y, o, ν) is finite.

Lemma 4.2. If Y = (Y, o, ν
) is a finite directed colored NPC complex, then Y (1) = ( Y (1) , o, ν) is a directed median graph with at most |V (Y )| isomorphism types of colored principal filters. In particular, if (Y, o) is a finite directed NPC complex, then ( Y (1) , o) is a directed median graph with at most |V (Y )| isomorphism types of principal filters.

Proof. Consider a covering map

ϕ : Y = ( Y , o, ν) → Y = (Y, o, ν).
We first show that ( Y (1) , o) is a directed median graph. By Theorem 3.7, Y (1) is a median graph. Since the image of a square in Y (1) is a square in Y , since ϕ preserves the direction of the edges, and since two opposite edges of a square of Y have the same direction, any two opposite edges of a square of Y (1) have the same direction. Consequently, Y (1) is a directed median graph.

Consider now two vertices u, u ∈ V ( Y ) such that ϕ( u) = ϕ( u ). In the following, we show that F o ( u, Y (1) ) and F o ( u , Y (1) ) are isomorphic, which implies that there are at most |V (Y )| different isomorphism types of colored principal filters by Lemma 4.1. The proof is based on the two following claims. The first claim can be easily proved by induction on the length of P .

Claim 1. For any path P = ( u = u 0 , u 1 , . . . , u k ) in Y , there exists a unique path

P = ( u = u 0 , u 1 , . . . , u k ) such that ϕ( u i ) = ϕ( u i ) for all 0 ≤ i ≤ k.
Claim 2. For any four paths

P 1 = ( u = u 0 , u 1 , . . . , u k ), P 1 = ( u = u 0 , u 1 , . . . , u k ), P 2 = ( u = v 0 , v 1 , . . . , v ), and P 2 = ( u = v 0 , v 1 , . . . , v ) in Y such that ϕ( u i ) = ϕ( u i ) for all 0 ≤ i ≤ k and ϕ( v j ) = ϕ( v j ) for all 0 ≤ j ≤ , we have u k = v if and only if u k = v .
Proof. For each 0 ≤ i ≤ k, let u i = ϕ( u i ) = ϕ( u i ) and for each 0 ≤ j ≤ , let v j = ϕ( v j ) = ϕ( v j ). Suppose that u k = v and consider the cycle Suppose that there exists 0 < i < k such that d( u, u i ) = n 1 (C). Suppose first that u i-1 = u i+1 . Then, since ϕ is an isomorphism between St( u i , Y ) and St(u i , Y ) and between St( u i , Y ) and St(u i , Y ), necessarily u i-1 = u i+1 . By induction hypothesis applied to the paths P 3 = ( u = u 0 , u 1 , . . . , u i-1 = u i+1 , . . . , u k ), P 3 = ( u = u 0 , u 1 , . . . , u i-1 = u i+1 , . . . , u k ), P 2 , and P 2 , we have u k = v and we are done. Assume now that u i-1 = u i+1 . Since the graph Y (1) is bipartite, we have

C = P 1 • P 2 = ( u = u 0 , u 1 , . . . , u k = v , v -1 , . . . , v 1 , v 0 = u). Let n 1 (C) = max{d( u,
d( u, u i-1 ) = d( u, u i+1 ) = n 1 (C) -1 and d( u i-1 , u i+1 ) = 2. Since Y (1) is median, there exists w i such that d( w i , u i-1 ) = d( w i , u i+1 ) = 1 and d( w i , u) = n 1 (C) -2. Note that u i u i-1 w i u i+1 is a square in St( u i , Y ).
Consequently, since ϕ is an isomorphism between St( u i , Y ) and St(u i , Y ) and between St( u i , Y ) and St(u i , Y ), there exists w i such that u i u i-1 w i u i+1 is a square in St( u i , Y ) and ϕ( w i ) = ϕ( w i ). By induction hypothesis applied to the paths P 4 = ( u = u 0 , u 1 , . . . , u i-1 , w i , u i+1 , . . . , u k ), P 4 = ( u = u 0 , u 1 , . . . , u i-1 , w i , u i+1 , . . . , u k ), P 2 , and P 2 , we have u k = v and we are done. Analogously, if there exists 0 < j < such that d( u, v j ) = n 1 (C), we can show that u k = v .

Suppose now that n (1) is median, there exists w such that d( w, u k-1 ) = d( w, v -1 ) = 1 and d( w, u) = n 1 (C) -2. Since ϕ( u k-1 ) = ϕ( u k-1 ), there exists a unique neighbor w of u k-1 such that ϕ( w ) = ϕ( w). Similarly, there exists a unique neighbor w of v -1 such that ϕ( w ) = ϕ( w). By induction hypothesis applied to the paths P 5 = ( u = u 0 , u 1 , . . . , u k-1 , w), P 5 = ( u = u 0 , u 1 , . . . , u k-1 , w ), P 6 = ( u = v 0 , v 1 , . . . , v -1 , w), and P 6 = ( u = v 0 , v 1 , . . . , v -1 , w ), we have that w = w . Consequently, since ϕ induces a bijection between St( w, Y ) and St(ϕ( w), Y ) and between St( w , Y ) and St(ϕ( w ), Y ) = St(ϕ( w), Y ), necessarily u k = v and we are done.

1 (C) = d( u, u k = v ) and n 2 (C) = 1. Since Y (1) is bipartite, d( u, u k-1 ) = d( u, v -1 ) = n 1 (C) -1 and d( u k-1 , v -1 ) = 2. Since Y
Define now a map f u, u from V ( Y ) to V ( Y ) such that f u, u ( u) = u . For any vertex v ∈ Y , consider a path P = ( u = u 0 , u 1 , . . . , u k = v) from u to v in Y . By Claim 1, there exists a unique path P = ( u = u 0 , u 1 , . . . , u k = v ) such that ϕ( u i ) = ϕ( u i ) for all 0 ≤ i ≤ k and we let f u, u ( v) = v . Note that ϕ(f ( v)) = ϕ( v) and by Claim 2, f ( v) is independent of the choice of the path P . Similarly, we can define a map f u , u from Y to Y such that f u , u ( u ) = u and one can easily see that

f u, u • f u , u = f u , u • f u, u = id. Consequently, f u, u is a bijection from V ( Y ) to V ( Y ). Moreover, from the definition of f u, u and from Claim 1, if v 1 v 2 is an edge of Y , then f u, u ( v 1 )f u, u ( v 2 ) is also an edge of Y . Since the orientation of v 1 v 2 in ( Y , o) is the same as the orientation of the edge v 1 v 2 = ϕ( v 1 )ϕ( v 2 ) in (Y, o), it is also the same as the orientation of f u, u ( v 1 )f u, u ( v 2 ) in ( Y , o). Furthermore since ν( v 1 v 2 ) = ν(v 1 v 2 ) = ν(f u, u ( v 1 )f u, u ( v 2 )), f u, u
preserves the colors of the edges of Y . Consequently, f u, u is an automorphism of Y = ( Y , o, ν) such that f u, u ( u) = u , and thus F o ( u, Y (1) ) and F o ( u , Y (1) ) are isomorphic. We will call an event structure E = (E, ≤, #) and its domain D(E) strongly regular if D(E) is isomorphic to a principal filter of the universal cover of some finite directed NPC complex. In view of Proposition 4.3, any strongly regular event structure is regular.

5. Thiagarajan's conjecture and special NPC complexes 5.1. Special NPC complexes. Consider an NPC complex Y , let Y be its universal cover and let ϕ : Y → Y be a covering map. Analogously to CAT(0) cube complexes, one can define the parallelism relation Θ on the set of edges E(Y ) of Y by setting that two edges of Y are in relation Θ iff they opposite edges of a common 2-cube of Y . Let Θ be the reflexive and transitive closure of Θ and let {Θ i : i ∈ I} denote the equivalence classes of Θ. For an equivalence class Θ i , the hyperplane H i associated to Θ i is the NPC complex consisting of the midcubes of all cubes of Y containing one edge of Θ i . The edges of Θ i are dual to the hyperplane H i . Let H(Y ) be the set of hyperplanes of Y .

The hyperplanes of an NPC complex Y do not longer satisfy the nice properties of the hyperplanes of CAT(0) cube complexes: they do not longer partition the complex in exactly two parts, they may self-intersect, self-osculate, two hyperplanes may at the same time cross and osculate, etc. Haglund and Wise [START_REF] Haglund | Special cube complexes[END_REF] detected five types of pathologies which may occur in an NPC complex (see Figure 3): We continue with the definition of each of these pathologies (in which we closely follow [25, Section 3]). Two hyperplanes H 1 and H 2 intersect if there exists a cube Q and two distinct midcubes A hyperplane H of Y self-intersects if it contains more than one midcube from the same cube, i.e., there exist two edges e 1 , e 2 dual to H that are consecutive in some square of Y (see Figure 3

Q 1 and Q 2 of Q such that Q 1 ⊆ H 1 and Q 2 ⊆ H 2 , i.e.,

(a)).

A hyperplane H is two-sided if N (H) is homeomorphic to the product H × (-1, 1), and there is a combinatorial map H × [-1, 1] → X mapping H × {0} identically to H. The hyperplane is one-sided if it is not two-sided (see Figure 3(b)). As noticed in [25, p.1562], requiring that the hyperplanes of Y are two-sided is equivalent to defining an orientation on the dual edges of H such that all sources of such edges belong to one of the sets H ×{-1}, H×{1} and all sinks belong to the other one. This orientation is obtained by taking the equivalence relation generated by elementary parallelism relation: declare two oriented edges e 1 and e 2 of Y elementary parallel if there is a square of Y containing e 1 and e 2 as opposite sides and oriented in the same direction. Notice that if (Y, o) is a directed NPC complex, then every hyperplane H of Y is two-sided. Conversely, if every hyperplane H of Y is two-sided, then Y admits admissible orientations (one can choose an admissible orientation for each hyperplane independently).

Let v be a vertex of Y and let e 1 , e 2 be two distinct edges incident to v but such that e 1 and e 2 are not consecutive edges in some square containing v. The hyperplanes H 1 and H 2 osculate at (v, e 1 , e 2 ) if e 1 is dual to H 1 and e 2 is dual to H 2 . The hyperplane H self-osculate at (v, e 1 , e 2 ) if e 1 and e 2 are dual to H. Consider a two-sided hyperplane H and an admissible orientation o of its dual edges. Suppose that H self-osculate at (v, e 1 , e 2 ). If v is the source of both e 1 and e 2 or the sink of both e 1 and e 2 , then we say that H directly self-osculate at (v, e 1 , e 2 ) (see Figure 3(c)). If v is the source of one of e 1 , e 2 , and the sink of the other, then we say that H indirectly self-osculate at (v, e 1 , e 2 ) (see Figure 3(d)). Note that a self-osculation of a hyperplane H is either direct or indirect, and this is independent of the orientation of the edges dual to H.

Two hyperplanes H 1 and H 2 inter-osculate if they both intersect and osculate (see Figure 3(e)).

Haglund and Wise [25, Definition 3.2] called an NPC complex Y special if its hyperplanes are two-sided, do not self-intersect, do not directly self-osculate, and no two hyperplanes interosculate. We show that strongly regular event structures obtained from finite special cube complexes admit regular trace labellings. If Y contains a self-intersecting hyperplane H, then there exist a square Q such that the four edges of Q are dual to H. Consider an admissible orientation o of Y and note that there exist two edges e 1 , e 2 in Q that have the same source v. In ( Y , o), consider a vertex v ∈ ϕ -1 (v) and note that v has two outgoing edges e 1 , e 2 such that ϕ( e 1 ) = e 1 and ϕ( e 2 ) = e 2 . Since λ H ( e 1 ) = λ H (e 1 ) = λ H (e 2 ) = λ H ( e 2 ), the labeling λ H violates the determinism condition in the principal filter (F o ( v, Y (1) ), ≺ o ).

If Y contains a hyperplane H that directly self-osculate at (v, e 1 , e 2 ), then there exists an orientation o of Y such that e 1 and e 2 have the same source v. In ( Y , o), consider a vertex v ∈ ϕ -1 (v) and note that v has two outgoing edges e 1 , e 2 such that ϕ( e 1 ) = e 1 and ϕ( e 2 ) = e 2 . Since λ H ( e 1 ) = λ H (e 1 ) = λ H (e 2 ) = λ H ( e 2 ), the labeling λ H violates the determinism condition in the principal filter (F o ( v, Y (1) ), ≺ o ).

Finally if Y contains two hyperplanes H 1 and H 2 that inter-osculate, then they osculate at (v, e 1 , e 2 ) and they intersect on a square Q. We can choose an orientation o of Y such that v is the source of both e 1 and e 2 . Then there exists a source u in Q that has two outgoing edges e 1 and e 2 that are parallel respectively to e 1 and e 2 . Let u ∈ ϕ -1 (u) and v ∈ ϕ -1 (v). Let e 1 , e 2 be the respective preimages of the edges e 1 , e 2 such that v is the source of e 1 , e 2 . Similarly, let e 1 , e 2 be the respective preimages of the edges e 1 , e 2 such that u is the source of e 1 , e 2 . Note that (1) ), ≺ o ). In D v , e 1 and e 2 correspond to two events that are in minimal conflict, and thus the pair ( λ H ( e 1 ), λ H ( e 2 )) does not belong to the independence relation I. On the other hand, in D u , e 1 and e 2 belong to a square, and thus they correspond to two concurrent events. Consequently, the pair ( λ H ( e 1 ), λ H ( e 2 )) belongs to I. Since λ H ( e 1 ) = λ H ( e 1 ) and λ H ( e 2 ) = λ H ( e 2 ), we have a contradiction.

λ H ( e 1 ) = λ H (e 1 ) = λ H (e 1 ) = λ H ( e 1 ) and λ H ( e 2 ) = λ H (e 2 ) = λ H (e 2 ) = λ H ( e 2 ). Consider the principal filters D v = (F o ( v, Y (1) ), ≺ o ) and D u = (F o ( u, Y
Conversely, suppose that Y is a finite special NPC complex. We define the independence relation I ⊆ H × H as follows: (H We show that λ H is a regular trace labeling of D with the trace alphabet (H, I). First note that if e 1 , e 2 are opposite edges of a square of D, then e 1 = ϕ( e 1 ) and e 2 = ϕ( e 2 ) are opposite edges of a square of Y and thus λ H ( e 1 ) = λ H (e 1 ) = λ H (e 2 ) = λ H ( e 2 ). Consequently, λ H is a labeling of the edges of D. From Lemma 4.2, D has at most |V (Y )| isomorphism types of colored principal filters. Therefore, in order to show that λ H is a regular trace labeling of D, we just need to show that λ H satisfies the conditions (LES1),(LES2), and (LES3).

For any two hyperplanes H 1 , H 2 in minimal conflict in D, there exist an edge e 1 dual to H 1 and an edge e 2 dual to H 2 such that e 1 and e 2 have the same source u. Note that since H 1 and H 2 are in conflict, e 1 and e 2 do not belong to a common square of D. Moreover, if e 1 and e 2 in a square Q in Y , then since there is a directed path from v to u, and since u is the source of Q, all vertices of Q are in (F o ( v, Y (1) ), ≺ o ) = D. Consequently, the hyperplane H 1 and H 2 osculate at ( u, e 1 , e 2 ) in Y . Let u = ϕ( u), e 1 = ϕ( e 1 ), and e 2 = ϕ( e 2 ), and note that u is the source of e 1 and e 2 . Let H 1 and H 2 be the hyperplanes of Y that are respectively dual to e 1 and e 2 . Since ϕ is a covering map, e 1 and e 2 do not belong to a common square. Consequently, H 1 and H 2 osculate at (u, e 1 , e 2 ). If A finite NPC complex X is called virtually special [START_REF] Haglund | Special cube complexes[END_REF][START_REF] Haglund | A combination theorem for special cube complexes[END_REF] if X admits a finite special cover, i.e., there exists a finite special NPC complex Y and a covering map ϕ : Y → X. We will call a strongly regular event structure E = (E, ≤, #) and its domain D(E) cover-special if D(E) is isomorphic to a principal filter of the universal cover of some virtually special complex with an admissible orientation.

H 1 = H 2 , H 1 directly self-osculates at (u, e 1 , e 2 ), which is impossible because Y is special. Consequently, λ H ( e 1 ) = λ H (e 1 ) = H 1 is different from λ H ( e 2 ) = λ H (e 2 ) =
Theorem 5.2. Any cover-special event structure E admits a regular trace labelling, i.e., Thiagarajan's conjecture is true for cover-special event structures.

Proof. Let D = D(E) be the domain of E and suppose that D is the principal filter D = (F o ( v, X (1) ), ≺ o ) of ( X, o) for a virtually special complex X and an admissible orientation o of its edges. Let Y be a finite special cover of X and let ϕ : Y → X be a covering map. Let o be the orientation of the edges of Y obtained from o via ϕ. Note that (X, o) and (Y, o ) have the same universal cover ( X, o) = ( Y , o )

In particular, the principal filter

D = (F o ( v, X (1) ), ≺ o ) of ( X, o) is the principal filter (F o ( v, Y (1) ), ≺ o ) of ( Y , o
). Since Y is finite and special, by Proposition 5.1 there exists an independence relation I on the hyperplanes (1) ), ≺ o ) is a regular trace labeling with the trace alphabet (H, I). Therefore, Thiagarajan's conjecture holds for the event domain D.

H = H(Y ) of Y such that the canonical labeling λ H of D = (F o ( v, Y

5.3.

Strongly hyperbolic regular event structures. In this subsection, we show that Thiagarajan's conjecture holds for a large and natural class of strongly regular event structures, namely those arising from hyperbolic CAT(0) cube complexes. It turns out that strongly hyperbolic regular event structures are cover-special. This is a consequence of the solution by Agol [START_REF] Agol | The conjecture[END_REF] of the virtual Haken conjecture for hyperbolic 3-manifolds. This breakthrough result of Agol is based on the theory of special cube complexes developed by Haglund and Wise [START_REF] Haglund | Special cube complexes[END_REF][START_REF] Haglund | A combination theorem for special cube complexes[END_REF].

Similarly to nonpositive curvature, Gromov hyperbolicity is defined in metric terms. However, as for the CAT(0) property, the hyperbolicity of a CAT(0) cube complex can be expressed in purely combinatorial way. A d) is δ-hyperbolic [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF][START_REF] Gromov | Hyperbolic groups[END_REF] if for any four points v, w, x, y of X, the two largest of the distance sums d(v, w) + d(x, y), d(v, x) + d(w, y), d(v, y) + d(w, x) differ by at most 2δ ≥ 0. A graph G = (X, E) endowed with its standard graph-distance d G is δ-hyperbolic if the metric space (X, d G ) is δ-hyperbolic. In case of geodesic metric spaces and graphs, δ-hyperbolicity can be defined in other equivalent ways, e.g., via thin or slim geodesic triangles. For example, a geodesic metric space (X, d) is 2δ-hyperbolic, if all geodesic triangles ∆(x, y, z) of (X, d) are δ-slim, i.e., for any point u on the side [x, y] the distance from u to [x, z] ∪ [z, y] is at most δ. This definition expresses the negative curvature of a geodesic metric space. A metric space (X, d) is hyperbolic if there exists δ < ∞ such that (X, d) is δ-hyperbolic. In case of median graphs, i.e., of 1-skeletons of CAT(0) cube complexes, the hyperbolicity can be characterized in the following way: [START_REF] Chepoi | Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs[END_REF][START_REF] Hagen | Weak hyperbolicity of cube complexes and quasi-arboreal groups[END_REF]). Let X be a CAT(0) cube complex. Then its 1-skeleton X (1) is hyperbolic if and only if all isometrically embedded square grids are uniformly bounded.

Lemma 5.3 ([
We call an event structure E = (E, ≤, #) and its domain D(E) hyperbolic if D(E) is isomorphic to a principal filter of a directed CAT(0) cube complex, whose 1-skeleton is hyperbolic. We call an event structure E = (E, ≤, #) and its domain D(E) strongly hyperbolic regular if there exists a finite directed NPC complex (X, o) such that X is hyperbolic and D is a principal filter of ( X (1) , o). Note that an event structure can be strongly regular and hyperbolic without being strongly regular hyperbolic (see Remark 7.2).

Hyperbolic CAT(0) cube complexes with uniformly bounded degrees have several strong and nice properties. It was shown in [START_REF] Haglund | Aspects combinatoires de la théorie géométrique des groupes[END_REF] that such CAT(0) cube complexes can be isometrically embedded into the Cartesian product of finitely many trees. Analogously to the nice labeling conjecture of [START_REF] Rozoy | Event structures and trace monoids[END_REF], a similar result does not hold for general CAT(0) cube complexes of uniformly bounded degrees [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF]. Modifying the arguments of [START_REF] Haglund | Aspects combinatoires de la théorie géométrique des groupes[END_REF] it can be shown that hyperbolic event structures with bounded degrees admit finite nice labelings (these labelings are not necessarily regular). Again this does not hold for general event structures (see Subsection 3.4).

The main result of this section is based on the following very deep and important result of Agol [START_REF] Agol | The conjecture[END_REF], following much work of Haglund and Wise [START_REF] Haglund | Special cube complexes[END_REF][START_REF] Haglund | A combination theorem for special cube complexes[END_REF]. Agol's original result is formulated in group-theoretical terms. Its following reformulation (see, for example, [START_REF] Bridson | Cube complexes, subgroups of mapping class groups, and nilpotent genus[END_REF]Theorem 6.7]) in the particular case of finite NPC complexes is particularly appropriate for our purposes:

Theorem 5.4 ([1]
). Let X be a finite nonpositively curved cube complex. If the fundamental group π 1 (X) of X is hyperbolic, then X is virtually special.

The condition that π 1 (X) is hyperbolic is equivalent to the fact that the universal cover X of X is hyperbolic. Indeed, it is well-known that π 1 (X) acts properly by deck transformations on X; see [START_REF] Hatcher | Algebraic Topology[END_REF] and [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF]Remark 8.3(2)]. Since X is finite, this action of π 1 (X) on X is cocompact. Consequently, π 1 (X) acts properly and cocompactly by isometries on X. By Švarc-Milnor lemma [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF]Proposition 8.19], the Cayley graph of π 1 (X) is quasi-isometric to X. Since hyperbolicity is an invariant of quasi-isometry [14, Theorem 1.9], π 1 (X) is hyperbolic if and only if X is hyperbolic. Therefore, any finite NPC complex X that has a hyperbolic universal cover is virtually special. Theorem 5.5. Any strongly hyperbolic regular event structure admits a regular trace labeling, i.e., Thiagarajan's conjecture is true for strongly hyperbolic regular event structures.

Proof. Let D = D(E) be the domain of a strongly hyperbolic regular event structure E. Consider a finite NPC complex (X, o) such that X is hyperbolic and D is the principal filter (F o ( v, X (1) ), ≺ o ) for some v ∈ X. By Theorem 5.4 of Agol, finite NPC complexes with hyperbolic universal covers are virtually special, thus E is a cover-special event structure. By Theorem 5.2, Thiagarajan's conjecture is true for E. In this section, we construct the domain ( W v , ≺ o * ) of a regular event structure (with bounded -cliques) that does not admit a regular nice labeling. To do so, we start with a directed colored CSC (complete square complex) X introduced by Wise [START_REF] Wise | Complete square complexes[END_REF]. Recall that in such complexes, the edges are classified vertical or horizontal, each edge has an orientation and a color, and any two incident edges belong to a square. 6.1. Wise's square complex X and its universal cover X. The complex X consists of six squares as indicated in Figure 4 (reproducing Figure 3 of [START_REF] Wise | Complete square complexes[END_REF]). Each square has two vertical and two horizontal edges. The horizontal edges are oriented from left to right and vertical edges from bottom to top. Denote this orientation of edges by o. The vertical edges of squares are colored white, grey, and black and denoted a, b, and c, respectively. The horizontal edges of squares are colored by single or double arrow, and denoted x and y, respectively. The six squares are glued together by identifying edges of the same color and respecting the directions to obtain the square complex X. Note that X has a unique vertex, five edges, and six squares. It can be directly checked that X is a complete square complex, and consequently (X, o) is a directed NPC complex. Let H X denote the subcomplex of X consisting of the 2 horizontal edges and let V X denote the subcomplex of X consisting of the 3 vertical edges.

The universal cover H X of H X is the 4-regular infinite tree F 4 . Its edges inherit the orientations from their images in H X : each vertex of H X has two incoming and two outgoing arcs. Analogously, the universal cover V X of V X is the 6-regular infinite tree F 6 where each vertex has three incoming and three outgoing arcs. Let v 1 be any vertex of H X . Then the principal filter of v 1 is the infinite binary tree T 2 rooted at v 1 : all its vertices except v 1 have one incoming and two outgoing arcs, while v 1 has two outgoing arcs and no incoming arc. Analogously, the principal filter of any vertex v 2 in the ordered set V X is the infinite ternary tree T 3 rooted at v 2 .

Let X be the universal cover of X and let ϕ : X → X be a covering map. Let X denote the support of X. Since X is a CSC, by [51, Theorem 3.8], X is the Cartesian product F 4 × F 6 of the trees F 4 and F 6 . The edges of X are colored and oriented as their images in X, and are also classified as horizontal or vertical edges. The squares of X are oriented as their images in X, thus two opposite edges of the same square of X have the same direction. This implies that all classes of parallel edges of X are oriented in the same direction. Denote this orientation of the edges of X by o. The 1-skeleton X (1) of X together with o is a directed median graph. Let v = ( v 1 , v 2 ) be any vertex of X, where v 1 and v 2 are the coordinates of v in the trees F 4 and F 6 . Then the principal filter F o ( v, X (1) ) of v is the Cartesian product of the principal filters of v 1 in F 4 and of v 2 in F 6 , i.e., is isomorphic to T 2 × T 3 .

By Lemma 4.1, the orientation of the edges of F o ( v, X (1) ) corresponds to the canonical basepoint orientation of F o ( v, X (1) ) with v as the basepoint. Moreover, by Proposition 4.3, F o ( v, X (1) ) is the domain of a regular event structure with one isomorphism type of principal filters. We summarize this in the following result: Lemma 6.1. For any vertex v of X, F o ( v, X (1) ) is the domain of a regular event structure with one isomorphism class of futures. [START_REF] Badouel | Context-free event domains are recognizable[END_REF]. Let v = ( v 1 , v 2 ) be an arbitrary vertex of X, where v 1 and v 2 are defined as before. From the definition of the covering map, the loop of X colored y gives rise to a bi-infinite horizontal path P y of X (1) passing via v and whose all edges are colored y and are directed from left to right. Analogously, there exists a bi-infinite vertical path P c of X (1) passing via v and whose all edges are colored c and are directed from bottom to top.

The projection of P y on the horizontal factor F 4 is a bi-infinite path P h of F 4 passing via v 1 . Analogously, the projection of P c on the vertical factor F 6 is a bi-infinite path P v of F 6 passing via v 2 . Consequently, the convex hull conv(P y ∪ P c ) of P y ∪ P c in the graph X (1) is isomorphic to the Cartesian product of P h × P v of the paths P h and P v . Therefore the subcomplex of X spanned by conv(P y ∪ P c ) is a directed plane Π yc tiled into squares (recall that each square is of one of 6 types and its sides are colored by the letters a, b, c, x, y), see Figure 5. Wise showed that the plane Π yc is not tiled periodically by the preimages of the squares of X. Theorem 6.2 ([51, Theorem 5.3]). The plane Π yc tiled into squares is not doubly periodic.

In our counterexample we will use the following result of [START_REF] Wise | Complete square complexes[END_REF] that was used to show that the plane Π yc is not tiled periodically by the preimages of the squares of X. Denote by P + y the (directed) subpath of P y having v as a source (this is a one-infinite horizontal path). Analogously, let P + c be the (directed) subpath of P c having v as a source. The convex hull of P + y ∪ P + c is a quarter of the plane Π yc , which we denote by Π ++ yc . Any shortest path in X (1) from v to a vertex u ∈ Π ++ yc can be viewed as a word in the alphabet A = {a, b, c, x, y}. For an integer n ≥ 0, denote by y n the horizontal subpath of P + y beginning at v and having length n. Analogously, for an integer m ≥ 0, denote by c m the vertical subpath of P + c beginning at v and having length m. Let M n (m) denote the horizontal path of Π ++ yc of length n beginning at the endpoint of the vertical path c m . M n (m) determines a word which is the label of the side opposite to y n in the rectangle which is the convex hull of y n and c m (see Figure 5). Let M n (m) also denote this corresponding word. Proposition 6.3 ([51, Proposition 5.9]). For each n, the words {M n (m) : 0 ≤ m ≤ 2 n -1} are all distinct, and thus, every positive word in x and y of length n is M n (m) for some m. This proposition is called in [START_REF] Wise | Complete square complexes[END_REF] "period doubling". It immediately establishes Theorem 6.2 because it shows that the period of the infinite vertical strip of Π ++ yc of width n and bounded on the left by the path P + c has period 2 n . Alternatively, every positive word in x and y appears in Π ++ yc , and thus Π yc cannot be periodic. , where βF 4 is the first barycentric subdivision of F 4 and βF 6 is the first barycentric subdivision of F 6 . Additionally, ( βX, o ) is a directed CAT(0) square complex. We assign a type to each vertex of βX: the preimage of the unique vertex of X is of type 0 and is called a 0-vertex, the preimages of the middles of edges of X are of type 1 and are called 1-vertices, and the preimages of centers of squares of X are of type 2 and are called 2-vertices.

To encode the colors of the edges of X, we introduce our central object, the square complex W (whose edges are no longer colored). Let A = {a, b, c, x, y} and let r : A → {1, 2, 3, 4, 5} be a bijective map. The complex W is obtained from βX by adding to each 1-vertex z of βX a path R z of length r(α) if z is the middle of an edge colored α ∈ A in X. The path R z has one end at z (called the root of R z ) and z is the unique common vertex of R z and βX (we call such added paths R z tips).

The square complex W has 27 vertices: the unique vertex of X, the 6 vertices which are the barycenters of the original squares, 5 vertices which are the barycenters of the original edges of X, and 15 vertices which are new vertices lying on tips. The complex W has 49 edges: 10 corresponding to the 5 original edges that have been subdivided, 24 connecting the barycenters of the original squares to the barycenters of the original edges and 15 forming the tips. The complex W has 24 squares: 4 for each original square.

Denote by o * the orientation of the edges of W defined as follows: the edges of βX are oriented as in (βX, o ) and the edges of tips are oriented away from their roots (see the rightmost figure of Figure 6 for the encoding of the last square of Figure 4). As a result, we obtain a finite directed NPC square complex (W, o * ).

Consider the universal cover W of W . It can be viewed as the complex βX with a path of length r(α) added to each 1-vertex which encodes an edge of X of color α ∈ A. We say that the vertices of W lying only on tips are of type 3 and they are called 3-vertices. Let o * denote the orientation of the edges of W induced by the orientation o * of W . Then ( W , o * ) is a directed CAT(0) square complex. Since W is finite, by Proposition 4.3, the directed median graph ( W (1) , o * ) has a finite number of isomorphisms types of principal filters F o * ( z, W (1) ).

Let v be any 0-vertex of W . Denote by W v the principal filter F o * ( v, W (1) ) of v in ( W (1) , ≺ o * ). By Proposition 4.3, W v together with the partial order ≺ o * is the domain of a regular event structure, which we call Wise's event domain. Since vertices of different types of W are incident to a different number of outgoing squares, any isomorphism between two filters of ( W v , ≺ o * ) preserves the types of vertices. We summarize all this in the following: Proposition 6.4. ( W v , ≺ o * ) is the domain of a regular event structure. Any isomorphism between any two filters of ( W v , ≺ o * ) preserves the types of vertices.

6.4. ( W v , ≺ o * ) does not have a regular nice labeling. In this subsection we prove that the event structure associated with Wise's regular event domain is a counterexample to Thiagarajan's conjecture. Proof. Since W v is the principal filter of a 0-vertex v, W v contains all vertices of X located in the quarter of plane Π ++ yc of X, in particular it contains the vertices of the paths P + c and P + y . Notice also that W v contains the barycenters and the tips corresponding to the edges Π ++ yc . Suppose by way of contradiction that W v has a regular nice labeling λ. Since W v has only a finite number of isomorphism types of labeled filters, the vertical path P + c contains two 0vertices, z and z , which have isomorphic labeled principal filters. Let z be the end of the vertical subpath c k of P + c and z be the end of the vertical subpath c m of P + c , and suppose without loss of generality that k < m. Let n > 0 be a positive integer such that m ≤ 2 n -1. Consider the horizontal convex paths M n (k) and M n (m) of Π ++ yc of length n beginning at the vertices z and z , respectively. For any 0 ≤ i ≤ n, denote by z k,i the ith vertex of M n (k) (in particular, z k,0 = z ). Analogously, denote by z m,i the ith vertex of M n (m) (in particular, z m,0 = z ). In W v , the paths M n (k) and M n (m) give rise to two convex horizontal paths M * n (k) and M * n (m) obtained from M n (k) and M n (m) by subdividing their edges. Denote by u k,i the unique common neighbor of z k,i and z k,i+1 , 0 ≤ i < n, in M * n (k) (and in W (1) ). Analogously, denote by u m,i the unique common neighbor of z m,i and z m,i+1 , 0 ≤ i < n (see Figure 7). The paths M * n (k) and M * n (m) belong to the principal filters F o * ( z , W (1) ) and F o * ( z , W (1) ), respectively.

By Proposition 6.3, the words M n (k) and M n (m) are different. Let f be an isomorphism between the filters F o * ( z k,0 , W (1) ) and F o * ( z m,0 , W (1) ). Since the words M n (k) and M n (m) are different, from the choice of the lengths of tips in the complexes W and W it follows that f cannot map the path M * n (k) to the path M * n (m) by a vertical translation, i.e., there exists an index 0 ≤ j < n such that f ( z k,j+1 ) = z m,j+1 ; let i be the smallest such index. Set z := f ( z k,i+1 ) and u := f ( u k,i ). Since f preserves the types of vertices, z is a 0-vertex and u is a 1-vertex. Since f maps a convex path M * n (k) to a convex path, u is the unique common neighbor of z m,i and z. Since each 1-vertex is the barycenter of a unique edge of X and z = z m,i+1 , we deduce that u = u m,i . The edge z k,i u k,i is directed from z k,i to u k,i . Analogously the edges z m,i u m,i and z m,i u are directed from z m,i to u m,i and u, respectively. Since z k,i u k,i and z m,i u m,i are parallel edges, they define the same event and therefore λ( z k,i u k,i ) = λ( z m,i u m,i ). On the other hand, since f maps the edge z k,i u k,i to the edge z m,i u and since the map f preserves the labels, we have λ( z k,i u k,i ) = λ( z m,i u). As a result, z m,i has two outgoing edges, z m,i u m,i and z m,i u, having the same label, contrary to the assumption that λ is a nice labeling. This contradiction shows that ( W v , ≺ o * ) does not admit a regular nice labeling. By Proposition 4.3, ( W v , ≺ o * ) is the domain of a regular event structure, establishing that Conjectures 1.1 and 2.2 are false. This concludes the proof of the theorem. 6.5. ( W v , ≺ o * ) has bounded -cliques. In this section, we show that our counterexample to Thiagarajan's conjecture also provides a counterexample to Conjecture 2.3 (and thus to Conjecture 1.2) of Badouel et al [START_REF] Badouel | Context-free event domains are recognizable[END_REF]. In [START_REF] Badouel | Context-free event domains are recognizable[END_REF], the conjecture was stated for conflict event domains that are more general than the domain of event structures we consider in this paper. However, we show in the next proposition that their conjecture does not hold even for the domains of event structures. Proposition 6.6. Wise's event domain ( W v , ≺ o * ) has bounded -cliques. Consequently, ( W v , ≺ o * ) is a counterexample to Conjectures 1.2 and 2.3. v . We refer to the events of ( W v , ≺ * o * ) as vertical, horizontal, and tip-events depending of the type of edges from their parallelism class.

z k,0 z m,0 u m,0 z m,1 u m,i z m,i z m,n z m,i+1 u k,0 z k,1 u k,i z k,i z k,n z k,i+1 u z v
Claim. If e 1 e 2 and e 1 and e 2 are either both vertical or both horizontal, then e 1 # µ e 2 .

Proof. Without loss of generality, assume that both events e 1 and e 2 are vertical, and note that e 1 and e 2 cannot be concurrent. Suppose by way of contradiction that e 1 (3) e 2 . Then there exists an event e 3 such that e 1 e 3 , e 2 # µ e 3 and e 3 is co-initial with e 1 and e 2 at two different configurations. Since e 1 e 3 and e 1 is vertical, the event e 3 cannot be vertical or a tip-event. Hence e 3 is horizontal. From the definition of W v it follows that the horizontal and vertical edges come from the Cartesian product of two trees. Therefore any pair of horizontal and vertical events defines a square of W v , thus they are concurrent. This contradicts the fact that e 3 # µ e 2 and establishes the claim.

Let Q be a -clique of W v . We asserts that the size of Q is at most 11. Suppose that |Q| ≥ 12. From the definition of ( W , o * ) it follows that ( W v , ≺ o * ) has degree 5: the out-degree of any 0vertex is 5, the out-degree of any 1-vertex is either 4 or 5, the out-degree of any 2-vertex is 2, and the out-degree of any 3-vertex is either 0 or 1. This implies that the maximum number of events of Q that are pairwise concurrent or in minimal conflict is 5. From the definition of ( W v , ≺ o * ) it also follows that two tip-events cannot be concurrent or in minimal conflict. Also from condition (3) in the definition of it immediately follows that Q cannot contain two tip-events e 1 and e 2 such that e 1 (3) e 2 . Indeed, if this happen, then there exists an event e 3 such that e 1 e 3 , thus e 1 and e 3 cannot be tip-events. Consequently, the -clique Q contains at most one tip-event. Since |Q| ≥ 12, Q contains at least 6 vertical or horizontal events, say Q contains a subset Q of 6 vertical events. Since all events of Q are vertical, they are not pairwise concurrent. Since Q is a -clique and at most 5 events of Q can be pairwise in minimal conflict, this implies that Q must contain two events e 1 , e 2 such that e 1 (3) e 2 . But this is impossible by the claim. Therefore ( W v , ≺ o * ) is a regular conflict event domain with bounded -cliques and bounded degree. Since by Theorem 6.5 ( W v , ≺ o * ) does not admit a regular nice labeling, this shows that Conjecture 2.3 is false. Remark 6.7. In the proof of Proposition 6.6, we use the fact that any pair of horizontal and vertical events are concurrent. This property holds because X is a CSC (complete square complex). Note that the fact that X is a CSC is not an essential property of X in the proof of Theorem 6.5.

Consequently, if we want to adapt the proof of Theorem 6.5 to other square complexes to find other counterexamples to Thiagarajan's Conjecture 1.1, it may be sufficient to consider V Hcomplexes (see Section 7), but in order to use the arguments in the proof of Proposition 6.6 to find other counterexamples to Badouel et al.'s Conjecture 1.2, we need to consider complete square complexes.

Aperiodic tilings and regular event structures

Our counterexample ( W v , ≺ o * ) of a regular 2-dimensional event domain without a regular labeling heavily uses the fact that the universal cover X of Wise's complex X [51] contains a particular aperiodic tiled plane (that is called antitorus by Wise). In this section, we show that the relationship between the existence of aperiodic planes and nonexistence of regular labelings is more general. Namely, we explain how to obtain other counterexamples from 4-way deterministic aperiodic tile sets.

Tiles (or Wang-tiles) are unit squares with colored edges. The edges of a Wang tile are called top (or North), right (or East), bottom (or South) and left (or West) edges in a natural way. A tile set T is a finite collection of Wang-tiles, placed with their edges horizontal and vertical. A tiling is a mapping f : Z 2 → T that assigns a tile to each integer lattice point of the plane. A tiling f is valid if every two adjacent tiles have the same color on their common edge. Note that a tile may not be rotated or flipped, i.e., each tile has a bottom-top and left-right orientation. A tiling f is periodic with period (a, b) ∈ Z 2 \ {(0, 0)} if for every (x, y) ∈ Z 2 , f (x, y) = f (x + a, y + b). If there exists a valid periodic tiling with tiles of T , then there exists a valid doubly periodic tiling with tiles of T [START_REF] Robinson | Undecidability and nonperiodicity for tilings of the plane[END_REF], i.e., a valid tiling f and two integers a, b > 0 such that f (x, y) = f (x + a, y) = f (x, y + b) for every (x, y) ∈ Z 2 . A tile set T is called aperiodic if there exists a valid tiling with tiles of T , and there does not exist any periodic valid tiling with tiles of T .

Let T = {t 1 , . . . , t n } be a tile set. We consider each tile t i as a unit square whose edges are directed and colored. Suppose that each square t i has two vertical and two horizontal edges and suppose that the horizontal and the vertical edges of all squares are colored differently, i.e., the set of colors can be partitioned into horizontal colors and vertical colors. The horizontal edges are directed from left to right and the vertical edges are directed from bottom to top.

A Wang tile set is said to be NW-deterministic [START_REF] Kari | Deterministic aperiodic tile sets[END_REF], if within the tile set there does not exist two different tiles that have the same colors on their top and left edges. NE-deterministic, SW-deterministic, and SE-deterministic tile sets are defined analogously. A Wang tile set is 4-way deterministic [START_REF] Kari | Deterministic aperiodic tile sets[END_REF] if it is NW-, NE-, SW-, and SE-deterministic. Kari and Papasoglu [START_REF] Kari | Deterministic aperiodic tile sets[END_REF] presented a 4-way deterministic aperiodic tile set T KP .

Given a 4-way deterministic set of tiles T , let X(T ) = (X(T ), o, ν) be the finite square complex obtained by identifying all the vertices and gluing together the squares of T along the sides which have the same color respecting their orientation. Then X(T ) is a V H-complex that has a unique vertex. Consequently, the universal cover X(T ) of X(T ) is a CAT(0) V Hcomplex. Denote by W (T ) the finite directed NPC complex derived from X(T ) in the same way as the complex W was derived from Wise's complex X in Subsection 6.3 (taking the first barycentric subdivision and adding tips of different lengths to encode the different colors). Let ( W (T ) v , ≺ o * ) denote the 2-dimensional event domain derived from X(T ) in the same way as ( W v , ≺ o * ) was derived from X. Since ( W (T ) v , ≺ o * ) comes from the universal cover of the finite directed NPC complex W (T ), ( W (T ) v , ≺ o * ) is a strongly regular event structure. The following lemma establishes a connection between the existence of valid tilings for 4-way deterministic tile sets and the existence of directed planes in the universal covers of the derived V H-complexes. Lemma 7.1. For a 4-way deterministic tile set T , the following conditions are equivalent:

(i) there exists a valid tiling with the tiles of T ;

(ii) the universal cover X(T ) of the square complex X(T ) contains directed planes;

(iii) the strongly regular domain ( W (T ) v , ≺ o * ) is not hyperbolic.

Proof. The implication (i) ⇒ (ii) is trivial and the implication (ii) ⇒ (iii) follows from Lemma 5.3. Suppose now that ( W (T ) v , ≺ o * )) is not hyperbolic. Then by Lemma 5.3, for any integer k, the V H-complex W (T ) v contains a square grid of size 2k × 2k. The following claim implies that in such a grid, we can find a k × k directed square grid in the directed V H-complex ( W (T ) v , o * )).

Claim. For any vertical (respectively, horizontal) edge e going from u to w and for any two squares Q 1 , Q 2 in ( W (T ) v , o * )) intersecting on e, u cannot be the sink of both horizontal (respectively, vertical) edges of Q 1 and Q 2 incident to u.

Proof. By way of contradiction, assume that u is the sink of the horizontal edges e 1 = u 1 u of Q 1 and e 2 = u 2 u of Q 2 . By Lemma 4.1, u 1 , u 2 ∈ I( v, u) and the median m of u 1 , u 2 , and v is adjacent to u 1 , u 2 and at distance 2 from u. Consequently, u u 1 m u 2 is a square of W (T ) v and thus of W (T ) but since u u 1 and u u 2 are horizontal edges, this contradicts the fact that X(T ) is a V H-complex.

Consequently, we can tile arbitrary large squares of the plane with the tiles of T . By a folklore compactness result from tiling theory, this implies that we can find a valid tiling of the plane with the tiles of T , concluding the proof of (iii) ⇒ (i).

Note that if T is a 4-way deterministic aperiodic tile set, all the directed planes of X(T ) are tiled in an aperiodic way. In the case of the tile set of Wise [START_REF] Wise | Complete square complexes[END_REF] from Figure 4, the CAT(0) square complex X contains aperiodic directed planes but it also contains some periodic directed planes.

Remark 7.2. As explained in [START_REF] Kari | Deterministic aperiodic tile sets[END_REF]Section 4], the universal cover X(T ) of the complex X(T ) derived from a tile set T can contain periodic planes that are not directed. This may happen even if T does not tile the plane or if T is an aperiodic tile set.

For these reasons, if T does not tile the plane, the directed CAT(0) complexes X(T ) and W (T ) are not necessarily hyperbolic, even if all principal filters ( W v , ≺ o * ) are hyperbolic domains.

We now explain how to derive a counterexample to Thiagarajan's conjectures from any 4-way deterministic aperiodic tile set. Theorem 7.3. For any 4-way deterministic aperiodic tile set T , the NPC square complex W (T ) is not virtually special and the 2-dimensional event domain ( W (T ) v , ≺ o * ) does not admit a regular nice labeling.

Proof. Consider a 4-way deterministic aperiodic tile set T and the associated NPC square complexes X(T ) and W (T ). Since T tiles the plane, every vertex v ∈ X(T ) is contained in a directed colored plane Π of X(T ). Note that the support Π of Π is the product of a directed path containing only horizontal edges and of a directed path containing only vertical edges. Consequently, in the directed CAT(0) complex ( W (T ), o * ), every 0-vertex v is contained in a directed plane Π * where Π * is the first barycentric subdivision of Π. Consequently, the directed CAT(0) complex ( W (T ) v , o * ) contains a quarter of the directed plane Π * that we denote by Π * ++ . Note that Π * ++ is the barycentric subdivision of a quarter of plane Π ++ of the directed plane Π. Let P * H be the horizontal path of Π * ++ containing v. If we factorize the domain on the left over the equivalence classes of futures, we obtain the square complex on the right that is not an NPC square complex lengths at 1-vertices. However, it turned out that finding a regular nice labeling is not always possible even in the case of 2-dimensional event domains (even those arising from CSC). On the positive side, we proved that Thiagarajan's conjecture is true for cover-special event structures (recall that Nielsen and Thiagarajan established this conjecture for conflict-free event structures and Badouel et al. proved it for context-free event structures). As a consequence of deep results from geometric group theory by Agol and Haglund-Wise, we deduce that strongly hyperbolic regular event structures are cover-special, showing that Thiagarajan's conjecture holds for a large and natural class of event domains.

We conclude the paper with a list of open problems, and we hope that some of these problems will be solved positively. 8.2. Regular versus strongly regular event structures. In view of Proposition 4.3, any strongly regular event structure is regular. One can ask if the converse holds (this was also mentioned by a referee of a preliminary version of this paper [START_REF] Chalopin | A counterexample to Thiagarajan's conjecture on regular event structures[END_REF]): Question 8.1. Is any regular event structure strongly regular?

A natural way to derive a finite directed NPC complex from the domain D of a regular event structure E is to factorize D over all equivalence classes of futures (i.e., to identify in a single vertex all configurations having the same principal filter up to isomorphism). Unfortunately, this construction does not preserve the non-positive curvature of D. For example, consider a domain D as described on the left of Figure 8. In the figure, only a part of the domain is described: one has to imagine that the dashed arrows lead to the remaining part of the domain with the assumption that two nodes that have the same label have isomorphic principal filters. When we factorize the domain D over the equivalence classes of futures, we obtain the square complex on the left of Figure 8. Note that this square complex is not an NPC square complex as it contains three squares that intersect in a vertex and that pairwise intersect on edges and these three squares do not belong to a 3-cube.

This phenomenon does not arise if we consider V H-complexes and isomorphisms that preserve vertical and horizontal edges. More formally, the domain D = D(E) of an event structure E is a V H-domain if D is a V H-complex. In this case, E is called a V H-event structure and the events of E are partitioned into vertical and horizontal events. A V H-event structure E is V H-regular if E has finite degree and has a finite number of principal filters up to isomorphism preserving vertical and horizontal events. In this case, the domain D(E) is called a regular V H-domain.

Even in this case, we do not know how to define formally a directed NPC square complex according to the factorization mentioned above such that the original domain is a principal filter of the universal cover of this complex.

  of all configurations of E ordered by inclusion; (c , c) is a (directed) edge of the Hasse diagram of the poset (D(E), ⊆) if and only if c = c ∪ {e} for an event e ∈ E \ c. An event e is said to be enabled by a configuration c if e / ∈ c and c ∪ {e} is a configuration. Denote by en(c) the set of all events enabled at the configuration c. Two events are called co-initial if they are both enabled at some configuration c. Note that if e and e are co-initial, then either e# µ e or e e . It is easy to see that two events e and e are in minimal conflict e# µ e if and only if e#e and e and e are co-initial. The degree deg(E) of an event structure E is the least positive integer d such that |en(c)| ≤ d for any configuration c of E. We say that E has finite degree if deg(E) is finite. The future (or the (principal) filter) F(c) of a configuration c is the set of all configurations c containing c: F(c) = ↑ c := {c ∈ D(E) : c ⊆ c }, i.e., F(c) is the principal filter of c in the ordered set (D(E), ⊆).

Figure 1 .

 1 Figure 1. Two examples where e 1 (3) e 2 : e 1 e 3 and e 2 # µ e 3

  and # is # restricted to E × E . It can be easily seen that the domain D(E\c) of the event structure E\c is isomorphic to the principal filter F(c) of c in D(E) such that any configuration c of D(E) corresponds to the configuration c \ c of D(E\c).

  As usual, Σ * is the set of finite words with letters in Σ. The independence relation I induces the equivalence relation ∼ I , which is the reflexive and transitive closure of the binary relation ↔ I : if σ, σ ∈ Σ * and (a, b) ∈ I, then σabσ ↔ I σbaσ . The relation D := (Σ × Σ) \ I is called the dependence relation. An M -labeled event structure is a labeled event structure E φ = (E, λ), where E = (E, ≤, #) is an event structure and λ : E → Σ is a labeling function which satisfies the following conditions: (LES1) e# µ e implies λ(e) = λ(e ), (LES2) if e e or e# µ e , then (λ(e), λ(e )) ∈ D, (LES3) if (λ(e), λ(e )) ∈ D, then e ≤ e or e ≤ e or e#e .

Theorem 3 . 7 (

 37 [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF]). The (undirected) Hasse diagram of the domain (D(E), ⊆) of any event structure E = (E, ≤, #) is a median graph. Conversely, for any median graph G and any basepoint v of G, the pointed median graph G v is isomorphic to the Hasse diagram of the domain of an event structure.

4. 1 .

 1 Directed median graphs. A directed median graph is a pair (G, o), where G is a median graph and o is an orientation of the edges of G in a such a way that opposite edges of squares of G have the same direction. By transitivity of Θ, all edges from the same parallelism class Θ i of G have the same direction. Since each Θ i partitions G into two parts, o defines a partial order ≺ o on the vertex-set

Lemma 4 . 1 .

 41 For any vertex v of a directed median graph (G, o), the following holds:(i) F o (v, G) induces a convex subgraph of G; (ii) the restriction of the partial order ≺ o on F o (v, G) coincides with the restriction of the canonical basepoint order ≤ v on F o (v, G); (iii) F o (v, G) together with ≺ o is the domain of an event structure; (iv) for any vertex u ∈ F o (v, G), the principal filter F o (u, G) is included in F o (v, G) andF o (u, G) coincides with the principal filter of u with respect to the canonical basepoint order ≤ v on F o (v, G).

  be a shortest path of G between v and u passing via u . By what we have shown in (i), in the Hasse diagram of ≺ o all the edges of P (v, u)

  w) : w ∈ C} and n 2 (C) = |{ w : d( u, w) = n 1 (C)}|. We prove the claim by lexicographic induction on (n 1 (C), n 2 (C)). If n 1 (C) = 0, then k = = 0 and we are done. Suppose now that n 1 (C) ≥ 1.

Proposition 4 . 3 .

 43 Consider a finite (uncolored) directed NPC complex (Y, o). Then for any vertex v of the universal cover Y of Y , the principal filter F o ( v, Y(1) ) with the partial order ≺ o is the domain of a regular event structure with at most |V (Y )| different isomorphism types of principal filters.Proof. By Theorem 3.3, Y is a CAT(0) cube complex. Combining Lemma 4.1 (iii)-(iv) and Lemma 4.2, we deduce that (F o ( v, Y(1) ), ≺ o ) is the domain of a regular event structure with at most |V (Y )| different isomorphism types of principal filters.

  (a) self-intersecting hyperplane; (b) one-sided hyperplane; (c) directly self-osculating hyperplane; (d) indirectly self-osculating hyperplane; (e) a pair of hyperplanes, which both intersect and osculate.

Figure 3 .

 3 Figure 3. A self-intersecting hyperplane (a), a one-sided hyperplane (b), a directly self-intersecting hyperplane (c), an indirectly self-intersecting hyperplane (d), and a pair of hyperplanes that inter-osculate (e).

5. 2 .

 2 Trace labelings of special event structures. Consider a finite NPC complex Y and let H = H(Y ) be the set of hyperplanes of Y . We define a canonical labeling λ H : E(Y ) → H by setting λ H (e) = H if the edge e is dual to H. For any covering map ϕ : Y → Y , λ H is naturally extended to a labeling λ H of E( Y ) where λ H (e) = λ H (ϕ(e)).

Proposition 5 . 1 .

 51 A finite NPC complex Y with two-sided hyperplanes is special if and only if there exists an independence relation I on H = H(Y ) such that for any admissible orientation o Y , for any : Y → Y , and for any principal filter D = (F o ( v, Y (1) ), ≺ o ) of ( Y , o), the canonical labeling λ H is a regular trace labeling of D with the trace alphabet (H, I).Proof. Suppose first that there exists an independence relation I ⊆ H 2 such that for any admissible orientation o of Y , for any covering map ϕ : Y → Y , and any principal filter D of ( Y , o), λ H is a regular trace labeling of D with the trace alphabet (H, I).

Figure 4 . 6 .

 46 Figure 4. The 6 squares defining the complex X

5 Figure 5 . 6 . 2 .

 5562 Figure 5. Part of the plane Π ++ yc appearing in X

Figure 6 . 6 . 3 .

 663 Figure 6. A square of X and the corresponding subcomplexes in (βX, o ) and (W, o * )

Theorem 6 . 5 .

 65 ( W v , ≺ o * ) does not admit a regular nice labeling. Consequently, Conjectures 1.1 and 2.2 are false.

Figure 7 .

 7 Figure 7. To the proof of Theorem 6.5

F 1 F 2 F 2 F 3 F 3 F 1 F 2 F 3 F 1 Figure 8 .

 1223312318 Figure8. If we factorize the domain on the left over the equivalence classes of futures, we obtain the square complex on the right that is not an NPC square complex

  there exists a square with two consecutive edges e 1 , e 2 such that e 1 is dual to H 1 and e 2 is dual to H 2 .

  1 , H 2 ) ∈ I if and only if the hyperplanes H 1 and H 2 intersect. From its definition, the binary relation I is symmetric. Since no hyperplane of Y self-intersects, I is also irreflexive, and thus (H, I) is a finite trace alphabet. and consider the principal filter D = (F o ( v, Y (1) ), ≺ o ). By Proposition 4.3, D is the domain of a regular event structure E. As explained in Subsection 3.3, the events of E are the hyperplanes of D. Hyperplanes H and H are concurrent if and only if they cross, and H ≤ H if and only if H = H or H separates H from v. The events H and H are in conflict iff H and H do not cross and neither separates the other from v. Note that this implies that H H iff H separate H from v and H and H osculate, and H# µ H iff H and H osculate and neither of H and H separates the other from v. Notice also that each hyperplane H of D is the intersection of a hyperplane H of Y with D.

Consider an admissible orientation o of Y , a vertex v ∈ V ( Y ), a covering map ϕ : Y → Y

  H 2 , establishing (LES1). Moreover, since no two hyperplanes of Y interosculate, we know that H 1 and H 2 do not intersect, and thus (H 1 , H 2 ) / ∈ I, establishing (LES2) when H 1 # µ H 2 . Suppose now that H 1 H 2 in D. There exist an edge e 1 dual to H 1 and an edge e 2 dual to H 2 such that the sink u of e 1 is the source of e 2 . Since H 1 separates H 2 from v in D, H 1 also separates H 2 from v in Y . Consequently, e 1 and e 2 do not belong to a common square of Y and the hyperplanes H 1 and H 2 osculate at ( u, e 1 , e 2 ). Let u = ϕ( u), e 1 = ϕ( e 1 ), and e 2 = ϕ( e 2 ), and note that u is the sink of e 1 and the source of e 2 . Let H 1 and H 2 be the hyperplanes of Y that are respectively dual to e 1 and e 2 . Since ϕ is a covering map, e 1 and e 2 do not belong to a common square. Consequently, H 1 and H 2 osculate at (u, e 1 , e 2 ). If H 1 = H 2 , then since I is irreflexive, (H 1 , H 1 ) / ∈ I. If H 1 = H 2 , since no two hyperplanes of Y inter-osculate, we know that H 1 and H 2 do not intersect, and thus (H 1 , H 2 ) / ∈ I, establishing (LES2) when H 1 H 2 . We prove (LES3) by contraposition. Consider two hyperplanes H 1 , H 2 that are concurrent, i.e., they intersect in D. Since H 1 and H 2 intersect in Y , there exists a square Q containing two consecutive edges e 1 , e 2 that are respectively dual to H 1 , H 2 . Let H 1 and H 2 be the hyperplanes of Y that are respectively dual to e 1 = ϕ( e 1 ) and e 2 = ϕ( e 2 ). Note that λ H ( e 1 ) = H 1 and λ H ( e 2 ) = H 2 . Since ϕ is a covering map, e 1 and e 2 belong to a square in Y . Then H 1 and H 2 intersect, and therefore (H 1 , H 2 ) ∈ I, establishing (LES3).

Acknowledgements. We are grateful to P.S. Thiagarajan for some email exchanges on Conjecture 1 and paper [36] and to our colleague R. Morin for several useful discussions. The work on the results not presented in the preliminary version [16] (Sections 5 and 7) was supported by ANR project DISTANCIA (ANR-17-CE40-0015).

Suppose ( W (T ) v , ≺ o * ) admits a regular nice labeling λ. This implies that there exist two 0-vertices y, y ∈ V (P * H ) that have isomorphic labeled principal filters. Let P * V and P * V be the vertical paths of Π * ++ containing respectively y and y . Let P * V = ( y = y 0 , u 0 , y 1 , u 1 , . . . , y j , u j , . . .) and P * V = ( y = y 0 , u 0 , y 1 , u 1 , . . . , y j , u j . . .). Note that for every j, y j and y j are 0-vertices while u j and u j are 1-vertices. Note that P V = ( y = y 0 , y 1 , . . . , y j , . . .) and P V = ( y = y 0 , y 1 , . . . , y j , . . .) are paths of Π ++ .

Note that for any j, y j u j and y j u j are parallel edges as well as u j y j+1 and u j y j+1 . Consequently, λ( y j u i ) = λ( y j u i ) and λ( u j y j+1 ) = λ( u j y j+1 ). Since λ is a nice labeling (and thus is deterministic), and since y and y have isomorphic labeled principal filters, one can easily show by induction on j that for any j, y j and y j (respectively, u j and u j ) have isomorphic labeled principal filters. Consequently, for any j, the tips attached to u j and u j have the same length, i.e., the edges y j y j+1 and y j y j+1 have the same color ν( y j y j+1 ) = ν( y j y j+1 ) in X(T ).

Since λ is a regular nice labeling of ( W (T ) v , ≺ o * ), there exists 0 ≤ k < m such that y k and y m have isomorphic labeled principal filters. Let P * k and P * m be the horizontal paths of Π * ++ going respectively from y k to y k and from y m to y m . Let be the distance from y k to y k in X(T ) and let P * k = ( y k = y k,0 , u k,0 , y k,1 , u k,1 , . . . , u k, -1 , y k, = y k ) and P * m = ( y m = y m,0 , u m,0 , y m,1 , u m,1 , . . . , u m, -1 , y m, = y m ). Note that P k = ( y k = y k,0 , y k,1 , . . . , y k, = y k ) and P m = ( y m = y m,0 , y m,1 , . . . , y m, = y m ) are paths of the plane Π. Using the same arguments as for P *

V and P * V , one can show that for any 0 ≤ i ≤ -1, the edges y k,j y k,j+1 and y m,j y m,j+1 have the same color ν( y k,j y k,j+1 ) = ν( y k,j y k,j+1 ) in X(T ).

Consider the rectangle R of Π with corners y k , y m , y m , and y k . For any k ≤ j < m, ν( y j y j+1 ) = ν( y j y j+1 ) in X(T ), i.e., the same sequence of colors appears on both vertical sides of R. Similarly, the same sequence of colors appears on both horizontal sides of the rectangle R. Since we can tile the plane by using copies of R, it is possible to find a periodic tiling of the plane using tiles of T . But this is impossible, since T is an aperiodic tile set. Consequently, the 2-dimensional event domain ( W (T ) v , ≺ o * ) does not admit a regular nice labeling, and by Theorem 5.2, W (T ) is not virtually special.

Using the tile set T KP of [START_REF] Kari | Deterministic aperiodic tile sets[END_REF], Lukkarila [START_REF] Lukkarila | The 4-way deterministic tiling problem is undecidable[END_REF] proved that for 4-way deterministic tile sets the tiling problem is undecidable. An immediate consequence of this result and of Theorem 7.3 is that there exists an infinite number of counterexamples to Conjecture 1.1.

Remark 7.4. Note that the V H-complex W (T ) derived from a 4-way deterministic tile set T is not necessarily a CSC complex. Consequently, we cannot directly generalize the proof of Proposition 6.6 to show that if T is aperiodic, then ( W (T ) v , ≺ o * ) is a counterexample to Conjecture 1.2 (see Remark 6.7).

Conclusions and open questions

8.1. Conclusions. In this paper, we presented an example of a regular event domain ( W v , ≺ o * ) with bounded degree and bounded -cliques which does not admit a regular nice labeling, providing a counterexample to Conjecture 1.1 of Thiagarajan [START_REF] Thiagarajan | Regular trace event structures[END_REF][START_REF] Thiagarajan | Regular event structures and finite Petri nets: A conjecture[END_REF] and Conjecture 1.2 of Badouel, Darondeau, and Raoult [START_REF] Badouel | Context-free event domains are recognizable[END_REF]. Furthermore, we show that this counterexample is not singular and that, in fact, there exists an infinite number of counterexamples to Conjecture 1.1 arising from the 4-way deterministic aperiodic tile sets constructed by Kari-Papasoglu [START_REF] Kari | Deterministic aperiodic tile sets[END_REF] and Lukkarilla [START_REF] Lukkarila | The 4-way deterministic tiling problem is undecidable[END_REF].

The event domain ( W v , ≺ o * ) is a principal filter of a directed 2-dimensional CAT(0) cube complex which is the universal cover of a finite directed colored CSC. At first, one can think that after trees, such cube complexes are the next simplest event domains on which Conjectures 1.1 or 1.2 must be true. Moreover, it was shown in [START_REF] Chepoi | On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes[END_REF] that any 2-dimensional CAT(0) cube complex of bounded degree admits a finite nice labeling. A finite nice labeling of W v can be also directly derived from the fact that W is a product of two trees with attached tips of various Question Does V H-domain occur a principal filter of the universal cover of some finite directed V H-complex? 8.3. Hyperbolic event domains. There are several natural reasons to investigate hyperbolic event domains. Similarly to CAT(0) and NPC spaces, Gromov hyperbolicity is defined by a metric condition. However, similarly to the CAT(0) property, the hyperbolicity of a CAT(0) cube complex can be expressed in purely combinatorial way, by requiring that all isometric square grids have bounded size. Theorem 5.5 establishes that Thiagarajan's conjecture is true for strongly hyperbolic regular event structures. We conjecture that this result can be generalized in the following way: Conjecture 8.3. Any strongly regular event structure with a hyperbolic domain admits a regular nice labeling. Conjecture 1.2 was positively solved by Badouel et al. [START_REF] Badouel | Context-free event domains are recognizable[END_REF] for context-free domains, which are particular hyperbolic domains:

Proof. Let G = (V, E) be a graph of uniformly bounded degree and v be an arbitrary root (basepoint) of G.

The vertices of F ∩ S i+1 (v) are called frontier points and this set is denoted by ∆(F ) [START_REF] Muller | The theory of ends, pushdown automata, and second-order logic[END_REF] and called a cluster. Let Φ(G) denote the set of all ends of G, i.e., the connected subgraphs of G(V \ S i (v)), when i ranges over the natural numbers. An end-isomorphism between two ends F and F of G is a mapping f between F and F such that f is a graph isomorphism and f maps ∆(F ) to ∆(F ). Then G is called a context-free graph [START_REF] Muller | The theory of ends, pushdown automata, and second-order logic[END_REF] if Φ(G) has only finitely many isomorphism classes under end-isomorphisms. Since G has uniformly bounded degree, each cluster ∆(F ) is finite. Moreover, from the definition of context-free graphs follows that a context-free graph G has only finitely many isomorphism classes of clusters, thus there exists a constant δ < ∞ such that the diameter of any cluster of G is bounded by δ. By [19, Proposition 12] any graph G whose diameters of clusters is uniformly bounded by δ is δ-hyperbolic (in fact, G is quasi-isometric to a tree).

The following conjecture generalizes Theorem 5.5, the results of [START_REF] Badouel | Context-free event domains are recognizable[END_REF] in the case of event structures considered in this paper, and Conjecture 8.3.

Conjecture 8.5. Conjectures 1.1 and 1.2 are true for hyperbolic event domains. By Lemma 5.3, the 1-skeleton X (1) of a CAT(0) cube complex is hyperbolic if and only if all isometrically embedded square grids are uniformly bounded. In the language of event structures, an isometrically embedded n × n grid H corresponds to a conflict-free event structure defined by 2n distinct events e 1 , . . . , e n , f 1 , . . . , f n such that any two events e i , f j are concurrent and any two events e i , e j or f i , f j are either causally dependent or concurrent. The isometricity follows from the fact that the events e 1 , . . . , e n , f 1 , . . . , f n are pairwise distinct. If this grid is embedded in a hypercube, then any two events e i , e j or f i , f j are concurrent. On the other hand, if e 1 e 2 • • • e n and f 1 f 2 • • • f n , then this grid is isometrically embedded as a directed flat square grid. A (directed) flat square grid of side n (respectively, a (directed) flat plane) of a median graph G is a (directed) n × n-grid H (respectively, Z × Z-grid) isometrically embedded in G such that any two squares of H sharing a common edge do not belong to a common 3-cube of G. Note that if H is a flat square grid or a flat plane of a median graph G, then H is a locally-convex subgraph of G, and by Lemma 3.2, H is a convex subgraph of G. This shows that if G contains a flat square grid of size n, then the graph Γ of the concurrent relation contains an induced complete bipartite subgraph K n,n . In a median graph not containing 3-cubes (i.e., 1-skeletons of 2-dimensional CAT(0) cube complexes), each embedded grid or plane is flat. We continue with a stronger version of Conjecture 8.5.

Conjecture 8.6. Conjectures 1.1 and 1.2 are true for event domains with uniformly bounded sizes of directed flat square grids.

A first solve this question could be to consider event structures such that the graph Γ does not admit induced complete bipartite subgraphs K n,n with arbitrarily large n.

Confusion-free domains.

As we noticed already, Conjecture 1.1 was positively solved by Nielsen and Thiagarajan [36] for conflict-free event structures. A possible way to generalize this result is to consider confusion-free domains.

Conflict-free event structures can be viewed as the event structures for which the minimalconflict graph Γ #µ is edgeless, i.e., each event of E is a connected component of Γ #µ . (Notice that conflict-free domains are not hyperbolic because they may contain Z n for any n.) Therefore, one way to extend the result of [36] is to consider more complex minimal-conflict graphs Γ #µ . One possible such extension is to consider the event structures whose minimal-conflict graphs Γ #µ are disjoint unions of cliques. Such event structures can be viewed as an extension of confusionfree event structures. An event structure E is confusion-free [START_REF] Nielsen | Petri nets, event structures and domains, part I[END_REF] if the reflexive closure of minimal conflict is transitive and e# µ e implies ↓ e \ {e} =↓ e \ {e } (we use the definition from [START_REF] Varacca | Probabilistic event structures and domains[END_REF]Proposition 2.4]). From the first condition it follows that for a confusion-free event structure the graph Γ #µ is a disjoint union of cliques. Confusion-free event structures correspond to deterministic concrete data structures [START_REF] Kahn | Concrete domains[END_REF] and to confusion-free occurrence nets [START_REF] Nielsen | Petri nets, event structures and domains, part I[END_REF].

Question 8.7. Do Conjectures 1.1 and 1.2 hold for confusion-free event structures? More generally, do they hold for event structures whose minimal-conflict graph Γ #µ is a disjoint unions of cliques? 8.5. Undecidability questions. We think that the relationship between the existence of aperiodic tile sets and the nonexistence of regular nice labelings of the associated event structures may help to prove some undecidability results. We conjecture that one cannot decide if a regular event structure satisfies Thiagarajan's conjecture: Conjecture 8.8. There does not exist an algorithm that, given a strongly regular event domain D, can determine whether or not D admits a regular nice labeling.

The intuition behind is that one can use Lukkarilla's construction [START_REF] Lukkarila | The 4-way deterministic tiling problem is undecidable[END_REF] to prove this conjecture. As in the proof of undecidability of the classical tiling problem [START_REF] Berger | The undecidability of the domino problem[END_REF][START_REF] Robinson | Undecidability and nonperiodicity for tilings of the plane[END_REF], the undecidability proof of Lukkarila is based on a reduction from the Turing machine halting problem. More precisely, for any Turing machine M, Lukkarila constructs a 4-way deterministic tile set T M such that either T M is an aperiodic tile set (this corresponds to the case when the Turing machine M does not halt), or T M does not tile the plane (this corresponds to the case when the Turing machine M halts). In the first case, by Theorem 7.3, the domain ( W (T M ) v , ≺ o * ) does not admit a regular nice labeling. In the second case, by Lemma 7.1, ( W (T M ) v , ≺ o * ) is a strongly regular domain that is hyperbolic. Consequently, if Conjecture 8.3 was true, ( W (T M ) v , ≺ o * ) would admit a regular nice labeling. This would prove Conjecture 8.8.

Another possible way to prove Conjecture 8.8 would be to anwser the following question in a positive way and use Theorem 5.2. Question 8.9. Given a 4-way deterministic tile set T such that there is no valid tiling with the tiles of T , is it true that the V H-complex W (T ) is virtually special? Note that if there was a positive answer to this question, this would answer a question of Agol [2, Question 3] and confirm the following conjecture of Bridson and Wilton [START_REF] Bridson | On the recognition problem for vitrually special cube complexes[END_REF]: Conjecture 8.10 ([13, Conjecture 1.2]). There does not exist an algorithm that, given a finite NPC square complex Y , can determine whether or not Y is virtually special. Indeed, in Lukkarila's construction, if the Turing machine M does not halt, then by Theorem 7.3 W (T M ) is not virtually special. On the other hand, if the Turing machine M halts, then if the answer to Question 8.9 was positive, W (T M ) would be virtually special.