Homology, Homotopy and Applications, vol.5(2), 2003, pp.39–82

TOPOLOGICAL DEFORMATION OF HIGHER DIMENSIONAL AUTOMATA

PHILIPPE GAUCHER and ERIC GOUBAULT

(communicated by Gunnar Carlsson)

Abstract

A local po-space is a gluing of topological spaces which are equipped with a closed partial ordering representing the time flow. They are used as a formalization of higher dimensional automata (see for instance [6]) which model concurrent systems in computer science. It is known [11] that there are two distinct notions of deformation of higher dimensional automata, “spatial” and “temporal”, leaving invariant computer scientific properties like presence or absence of deadlocks. Unfortunately, the formalization of these notions is still unknown in the general case of local po-spaces.

We introduce here a particular kind of local po-space, the “globular CW-complexes”, for which we formalize these notions of deformations and which are sufficient to formalize higher dimensional automata. The existence of the category of globular CW-complexes was already conjectured in [11].

After localizing the category of globular CW-complexes by spatial and temporal deformations, we get a category (the category of dihomotopy types) whose objects up to isomorphism represent exactly the higher dimensional automata up to deformation. Thus globular CW-complexes provide a rigorous mathematical foundation to study from an algebraic topology point of view higher dimensional automata and concurrent computations.

1. Introduction

Algebraic topological models have been used now for some years in concurrency theory (concurrent database systems and fault-tolerant distributed systems as well). The earlier models, progress graph (see [3] for instance) have actually appeared in operating systems theory, in particular for describing the problem of “deadly

Received October 11, 2001, revised July 16, 2002; published on April 22, 2003. 2000 Mathematics Subject Classification: 55P15,55U05,68Q85 Key words and phrases: homology, homotopy, concurrency, cubical set, CW-complex, higher dimensional automata, category, localization, partial order, partially ordered space \begin{matrix}c \\ ◯ \end{matrix} 2003, Philippe Gaucher and Eric Goubault. Permission to copy for private use granted.

embrace”^{1} in “multiprogramming systems”.

The basic idea is to give a description of what can happen when several processes are modifying shared resources. Given a shared resource a, we see it as its associated semaphore that rules its behaviour with respect to processes. For instance, if a is an ordinary shared variable, it is customary to use its semaphore to ensure that only one process at a time can write on it (this is mutual exclusion). A semaphore is nothing but a register which counts the number of times a shared object can still be accessed by processes. In the case of usual shared variables, this register is initialized with value 1, processes trying to access (read or write) on the corresponding variable compete in order to get it first, then the semaphore value is decreased: we say that the semaphore has been locked^{2} by the process. When it is equal to zero, all processes trying to access this semaphore are blocked, waiting for the process which holds the lock to relinquish it, typically when it has finished reading or writing on the corresponding variable: the value of the semaphore is then increased.

When the semaphores are initialized with value one, meaning that they are associated with shared variables accessed in a mutually exclusive manner, they are called binary semaphores. When a shared data (identified with its semaphore) can be accessed by one or more processes, meaning that the corresponding semaphore has been initialized with a value greater than one, it is called a counting semaphore.

Given n deterministic sequential processes Q_{1}, …, Q_{n}, abstracted as a sequence of locks and unlocks on (semaphores associated with) shared objects, Q_{i} = R^{1}a_{i}^{1}.R^{2}a_{i}^{2} ⋯ R^{n_{i}}a_{i}^{n_{i}} (R^{k} being P or V^{3}), there is a natural way to understand the possible behaviours of their concurrent execution, by associating to each process a coordinate line in ℝ^{n}. The state of the system corresponds to a point in ℝ^{n}, whose ith coordinate describes the state (or “local time”) of the ith processor.

Consider a system with finitely many processes running altogether. We assume that each process starts at (local time) 0 and finishes at (local time) 1; the P and V actions correspond to sequences of real numbers between 0 and 1, which reflect the order of the P ’s and V ’s. The initial state is (0, …, 0) and the final state is (1, …, 1). An example consisting of the two processes T_{1} = P a.P b.V b.V a and T_{2} = P b.P a.V a.V b gives rise to the two dimensional progress graph of Figure 1.

The shaded area represents states which are not allowed in any execution path, since they correspond to mutual exclusion. Such states constitute the forbidden area. An execution path is a path from the initial state (0, …, 0) to the final state (1, …, 1) avoiding the forbidden area and increasing in each coordinate - time cannot run backwards. We call these paths directed paths or dipaths. This entails that paths reaching the states in the dashed square underneath the forbidden region, marked “unsafe” are deemed to deadlock, i.e. they cannot possibly reach the allowed terminal state which is (1, 1) here. Similarly, by reversing the direction of time, the states in the square above the forbidden region, marked “unreachable”, cannot be reached from the initial state, which is (0, 0) here. Also notice that all

1as E. W. Dijkstra originally put it in [4], now more usually called deadlock. 2Of course this operation must be done “atomically”, meaning that the semaphore itself must be handled in a mutually exclusive manner: this is done at the hardware level. 3Using E. W. Dijkstra’s notation P and V [4] for respectively acquiring and releasing a lock on a semaphore.

Figure 1: Example of a progress graph

terminating paths above the forbidden region are “equivalent” in some sense, given that they are all characterized by the fact that T_{2} gets a and b before T_{1} (as far as resources are concerned, we call this a schedule). Similarly, all paths below the forbidden region are characterized by the fact that T_{1} gets a and b before T_{2} does.

On this picture, one can already recognize many ingredients that are at the center of the main problem of algebraic topology, namely the classification of shapes modulo “elastic deformation”. As a matter of fact, the actual coordinates that are chosen for representing the times at which P s and V s occur are unimportant, and these can be “stretched” in any manner, so the properties (deadlocks, schedules etc.) are invariant under some notion of deformation, or homotopy. This is only a particular kind of homotopy though, and this explains why a new theory has to be designed. We call it (in subsequent work) directed homotopy or dihomotopy in the sense that it should preserve the direction of time. For instance, the two homotopic shapes, all of which have two holes, of Figure 2 and Figure 3 have a different number of dihomotopy classes of dipaths. In Figure 2 there are essentially four dipaths up to dihomotopy (i.e. four schedules corresponding to all possibilities of accesses of resources a and b) whereas in Figure 3, there are essentially three dipaths up to dihomotopy.

Progress graphs have actually a nice topological model; they are compact order-Hausdorff spaces (see [26], [21]), i.e. are compact Hausdorff spaces with a closed (global) partial order. More general topological models are needed in general, in which the partial order is only defined locally, and have been introduced and motivated in [7], [5] and [6]. The precise definitions and properties are given in Section 3.1.

The natural combinatorial notion which discretizes this topological framework is that of a precubical set, which is a collection of points (states), edges (transi-Homology, Homotopy and Applications, vol. 5(2), 2003 42

Figure 2: The progress graph corresponding to P a.V a.P b.V b | P a.V a.P b.V b Figure 3: The progress graph corresponding to P b.V b.P a.V a | P a.V a.P b.V b tions), squares, cubes and hypercubes (higher-dimensional transitions representing the truly-concurrent execution of some number of actions). This is introduced in [27] as well as possible formalizations using n-categories, and a notion of homotopy. These precubical sets are called Higher-Dimensional Automata (HDA) following [27] because it really makes sense to consider a hypercube as some form of transition (as in transition systems, used in semantics of programming languages). We show the precise relation between this model and the new topological model we introduce here (“globular CW-complexes”) in Section 3.2, the relation between local po-spaces and cubical sets can be found in [6].

There are other formulations of the same problems using homological methods [15], strict globular ω-categories [12]. An important motivation in these pieces of work is that of “reducing the complexity” of the semantics (given by a local po-space for instance) by considering deformation retracts. The classification of the possible concurrent semantics (and behaviours) should then be the result finding the right “(di-)homotopy types”. This calls for a suitable notion of (di-)homotopy equivalence, and for starting with a reasonable category of local po-spaces. In the case of ordinary homotopy theory, we have to restrict to the category of CW-complexes; the category of topological spaces being far too big for practical purposes. The situation is even worse here, we not only have to restrict on the topology part, but also on the local po-structures.

We give in this paper a notion of CW-complex, called globular CW-complex which meets the basic requirements of what we expect to be a “directed cellular complex”. It has been obtained by mimicking the well-known concept of CW-complexes, but built from “directed” cells. This is the purpose of Section 2. Still in the same section, we introduce the fundamental functor called the globe functor, from the category of topological spaces to the category of po-spaces. This functor is the key to understanding how things work in the directed situation. In particular, it yields an embedding of the category of homotopy types into the new category of dihomotopy types (Theorem 5.9). This embedding has a lot of important consequences that are sketched in the perspectives section of [13].

Once the right notion has been given, we make explicit the link between the globular CW-complexes and some geometric notions above mentioned, that is the local po-spaces and the precubical sets in Section 3. We prove that every globular CWcomplex is a local po-space indeed (Theorem 3.3) and that there exists a geometric realization of any precubical set as a globular CW-complex (subsection 3.3).

Next in Section 4 we recast in the globular CW-complex framework the notion of spatial and temporal deformations informally presented in [11] and whose consequences are informally explored in [13]. For that we construct, by localization of the category of globular CW-complexes with respect to appropriate morphisms, three categories whose isomorphism classes of objects are exactly the globular CW-complexes modulo spatial deformations (Theorem 4.7), the globular CWcomplexes modulo temporal deformations (Theorem 4.12) and at last the globular CW-complexes modulo spatial and temporal deformations together (Theorem 4.16). This latter category will be called the category of dihomotopy types.

Then Section 5 is devoted to making explicit the link between homotopy types and dihomotopy types. The introduction of the path space of a globular CW-complex between two points of its 0-skeleton is the essential ingredient in the proof of Theorem 5.7 and Corollary 5.8. This allows us to derive the embedding theorem Theorem 5.9 which states that there exists an embedding of the category of homotopy types into that of dihomotopy types. This notion of path spaces also allows us to provide a conjectural statement for the analogue of the Whitehead theorem in the directed framework, and to check it in the case of globes.

Section 6 focuses on a very striking reason why it is necessary to work with “non-contracting” maps everywhere. It was not really possible to justify this axiom while the definition of globular CW-complexes was being given in Section 2. Only one reason is described. Indeed there are lots of other algebraic reasons which are out of the scope of this paper.

2. Globular CW-complexes

This section is devoted to the introduction of the category glCW of globular CW-complexes and to the comparison with the usual notion of CW-complex.

2.1. Closed partial order Definition 2.1. Let X be a topological space. A binary relation R on X is closed if the graph of R is a closed subset of the cartesian product X × X.

It is a well-known fact that any topological space X endowed with a closed partial order is necessarily Hausdorff (see for instance [26], [21]).

Definition 2.2. A pair (X, ⩽_{X}) where X is a topological space and ⩽_{X} a closed partial order is called a global po-space.

In most cases, the partial order of a global po-space X will be simply denoted by ⩽. Here are two fundamental examples of global po-spaces for the sequel :

1. The achronal segment 𝕀 is defined to be the segment [0, 1] endowed with the closed partial ordering x ⩽_{𝕀} y if and only if x = y.

2. The directed segment \overrightarrow{I} is defined to be the segment [0, 1] endowed with the closed partial ordering x ⩽\overrightarrow{I} y if and only if y − x is non-negative.

We will describe gluings of global po-spaces (i.e. local po-spaces) in Section 3.1.

2.2. The globe of a topological space

Let n ⩾ 1. Let D^{n} be the closed n-dimensional disk defined by the set of points (x_{1}, …, x_{n}) of ℝ^{n} such that x_{1}^{2} + ⋯ + x_{n}^{2} ⩽ 1 endowed with the topology induced by that of ℝ^{n}. Let S^{n−1} = ∂D^{n} be the boundary of D^{n} for n ⩾ 1, that is the set of (x_{1}, …, x_{n}) ∈ D^{n} such that x_{1}^{2} + ⋯ + x_{n}^{2} = 1. Notice that S^{0} is the discrete two-point topological space {−1, +1}. Let D^{0} be the one-point topological space. And let e^{n} := D^{n} − S^{n}.

The fundamental ingredient in all further constructions is the globe functor (Figure 4) defined below, which will give rise to a particular family of global po-spaces.

Loosely speaking the globe of a topological space X is the reduced suspension of X equipped with some closed partial ordering representing the time flow.

The underlying topological space of the globe of a topological space X, Glob(X), is therefore the quotient of the product space X × [0, 1] by the relations (x, 0) = (x′, 0) and (x, 1) = (x′, 1) for any x, x′ ∈ X. By convention, the equivalence class of (x, 0) (resp. (x, 1)) in Glob(X) will be denoted by \underline{ι} (resp. \underline{σ}). We can partially order Glob(X) using the standard order ⩽_{I} on I = [0, 1] as follows :

Proposition 2.3. Let X be a Hausdorff topological space and consider the partial ordering of X × I defined by R = {((x, t), (x, t′)), (x, t, t′) ∈ X × I × I and t ⩽_{I} t′}. Then its image by the canonical surjection s from X × I to Glob(X) is a closed partial ordering on Glob(X).

The partial order relation on Glob(X) is as follows:

• (x, 0) ⩽ (x′, t′) for all x, x′, t′ ∈ X × X × I,

• when t, t′ ∈]0, 1[×]0, 1[, (x, t) ⩽ (x′, t′) if and only if x = x′,

• (x′, t′) ⩽ (x, 1) for all x, x′, t′ ∈ X × X × I.

Proof. By the homeomorphism (x, t, x′, t′) ↦ (x, x′, t, t′) from X × I × X × I to X × X × I × I, one sees that R is a closed subset of X × I × X × I if and only if Diag(X) × {(t, t′) ∈ I × I, t ⩽ t′} is a closed subset of X × X × I × I where Diag(X) is the diagonal {(x, x)/x ∈ X} of X. Since X is Hausdorff, then its diagonal is closed and R as well. By definition of the quotient topology, s(R) is closed if and only if s^{−1} ∘ s(R) is a closed subset of X × I. It suffices then to notice that s^{−1} ∘ s(R) = ((X × {0}) × (X × I)) ∪ ((X × I) × (X × {1})) ∪ R to complete the proof.

Ordinary CW-complexes are built by gluing cells e^{n}. We want to define a directed version of CW-complexes, and the simplest way to do so is to add a “direction” to these cells. Every HDA can be seen indeed as a pasting of n-cubes or of n-globes, depending on whether one chooses the cubical approach or the globular approach to model the execution paths, the higher dimensional homotopies between them and the compositions between them (see Section 1 and [16] for more explanations). Loosely speaking, directed cells such as Glob(e^{n}) are “equivalent” modulo directed deformations to a n-cube with the usual cartesian partial ordering defined by (x_{1}, …, x_{n}) ⩽ (y_{1}, …, y_{n}) if and only if for any i, x_{i} ⩽ y_{i}.

2.3. Globular CW-complex : definition and examples

Let \overrightarrow{D}^{n+1} := Glob(D^{n}) and \overrightarrow{S}^{n+1} := Glob(S^{n}) for n ⩾ 0. Notice that there is a canonical inclusion of global po-spaces \overrightarrow{S}^{n} ⊂ \overrightarrow{D}^{n+1} for n ⩾ 1. By convention, let \overrightarrow{S}^{0} := \{0, 1\} with the trivial ordering (0 and 1 are not comparable). There is a canonical inclusion \overrightarrow{S}^{0} ⊂ \overrightarrow{D}^{1} such that 0 is mapped onto \underline{ι} (the initial state of \overrightarrow{D}^{1}) and 1 is mapped onto \underline{σ} (the final state of \overrightarrow{D}^{1}), which is a morphism of po-spaces.

Definition 2.4. For any n ⩾ 1, \overrightarrow{D}^{n} − \overrightarrow{S}^{n−1} together with the closed partial ordering induced by I is called the n-dimensional globular cell. More generally, every

Figure 4: Symbolic representation of Glob(X) for some topological space X

pair (X, ⩽), where X is a topological space and ⩽ a closed partial ordering on X, isomorphic to \overrightarrow{D}^{n} − \overrightarrow{S}^{n−1} for some n will be called a n-dimensional globular cell.

Now we are going to describe the process of attaching globular cells.

1. Start with a discrete set of points X^{0}.

2. Inductively, form the n-skeleton X^{n} from X^{n−1} by attaching globular n-cells \overrightarrow{e}_{α}^{n} via maps ϕ_{α} : \overrightarrow{S}^{n−1} ⟶ X^{n−1} with ϕ_{α}(\underline{ι}), ϕ_{α}(\underline{σ}) ∈ X^{0} such that^{4} : for every non-decreasing map ϕ from \overrightarrow{I} to \overrightarrow{S}^{n−1} such that ϕ(0) = \underline{ι} and ϕ(1) = \underline{σ}, there exists 0 = t_{0} < ⋯ < t_{k} = 1 such that ϕ_{α} ∘ ϕ(t_{i}) ∈ X^{0} for any 0 ⩽ i ⩽ k which must satisfy

(a) for any 0 ⩽ i ⩽ k − 1, there exists a globular cell of dimension d_{i} with d_{i} ⩽ n − 1 ψ_{i} : \overrightarrow{D}^{d_{i}} → X^{n−1} such that for any t ∈ [t_{i}, t_{i+1}], ϕ_{α} ∘ ϕ(t) ∈ ψ_{i}(\overrightarrow{D}^{d_{i}}) ;

(b) for 0 ⩽ i ⩽ k − 1, the restriction of ϕ_{α} ∘ ϕ to [t_{i}, t_{i+1}] is non-decreasing ;

(c) the map ϕ_{α} ∘ ϕ is non-constant ;

Then X^{n} is the quotient space of the disjoint union X^{n−1} ⨆_{α} \overrightarrow{D}_{α}^{n} of X^{n−1} with a collection of \overrightarrow{D}_{α}^{n} under the identification x ∼ ϕ_{α}(x) for x ∈ \overrightarrow{S}_{α}^{n−1} ⊂ ∂\overrightarrow{D}_{α}^{n}. Thus as set, X^{n} = X^{n−1} ⨆_{α} \overrightarrow{e}_{α}^{n} where each \overrightarrow{e}_{α}^{n} is a n-dimensional globular cell.

3. One can either stop this inductive process at a finite stage, setting X = X^{n}, or one can continue indefinitely, setting X = ⋃_{n} X^{n}. In the latter case, X is given the weak topology : a set A ⊂ X is open (or closed) if and only if A ∩ X^{n} is open (or closed) in X^{n} for some n (this topology is nothing else but the direct limit of the topology of the X^{n}, n ∈ ℕ). Such a X is called a globular CW-complex and X_{0} and the collection of \overrightarrow{e}_{α}^{n} and its attaching maps ϕ_{α} : \overrightarrow{S}^{n−1} ⟶ X^{n−1} is called the cellular decomposition of X.

4This condition will appear to be necessary in the sequel.

As for usual CW-complexes (see [20] Proposition A.2.), a globular cellular decomposition of a given globular CW-complex X yields characteristic maps ϕ_{α} : \overrightarrow{D}^{n_{α}} → X satisfying :

1. The mapping ϕ_{α} ↾_{\overrightarrow{D}^{nα} −\overrightarrow{S}^{nα−1}} induces an homeomorphism from \overrightarrow{e}^{n_{α}} to its image.

2. All the previous globular cells are disjoint and their union gives back X.

3. A subset of X is closed if and only if it meets the closure of each globular cells of X in a closed set.

We will consider without further mentioning that the segment \overrightarrow{I} is a globular CW-complex, with {0, 1} as its 0-skeleton.

Proposition and Definition 2.5. Let X be a globular CW-complex with characteristic maps (ϕ_{α}). Let γ be a continuous map from \overrightarrow{I} to X. Then γ([0, 1]) ∩ X^{0} is finite. Suppose that there exists 0 ⩽ t_{0} < ⋯ < t_{n} ⩽ 1 with n ⩾ 1 such that t_{0} = 0, t_{n} = 1, such that for any 0 ⩽ i ⩽ n, γ(t_{i}) ∈ X^{0}, and at last such that for any 0 ⩽ i ⩽ n − 1, there exists an α_{i} (necessarily unique) such that for t ∈ [t_{i}, t_{i+1}], γ(t) ∈ ϕ_{α_{i}}(\overrightarrow{D}^{n_{α}}). Then such a γ is called an execution path if the restriction γ ↾_{[t_{i},t_{i+1}]} is non-decreasing.

Proof. Obvious.

By constant execution paths, one means an execution paths γ such that γ([0, 1]) = {γ(0)} with γ(0) ∈ X^{0}. The points (i.e. elements of the 0-skeleton) of a given globular CW-complexes X are also called states. Some of them are fairly special:

Definition 2.6. Let X be a globular CW-complex. A point α of X^{0} is initial (resp. final) if for any execution path ϕ such that ϕ(1) = α (resp. ϕ(0) = α), then ϕ is the constant path α.

Proposition 2.7. If X is a CW-complex, then Glob(X) is a globular CW-complex by setting

Glob(X)^{0} = \{\underline{ι}, \underline{σ}\}

for x ∈ X.

Proof. Since X is a CW-complex, then it is described by cells and attaching maps. There exists topological spaces X^{n} with X = ⋃_{n} X^{n} with the weak topology and ϕ_{α} : S^{n−1} ⟶ X^{n−1} (for α belonging to some set of indexes) continuous maps which describe how to go from X^{n−1} to X^{n}; we have the following co-cartesian diagram of topological spaces:

[figure: S^{n−1}; ϕ_{α}; X^{n−1}; D^{n}; i; X^{n}]

where i is the inclusion of S^{n−1} into D^{n} as its boundary ∂D^{n}.

Let us describe inductively Glob(X) as a globular CW-complex. We begin by setting Glob(X)^{0} = \{\underline{ι}, \underline{σ}\}. Then we apply inductively the functor Glob(−) on the co-cartesian diagram above, to obtain a new co-cartesian diagram by Theorem 5.2 :

[figure: Glob(S^{n−1}) ≅ \overrightarrow{S}^{n}; Glob(ϕ_{α}); Glob(X^{n−1}); Glob(D^{n}) ≅ \overrightarrow{D}^{n+1}; Glob(i); Glob(X^{n})]

First of all, it is easy to see that Glob(i) induces a homeomorphism from \overrightarrow{S}^{n} onto the

boundary ∂\overrightarrow{D}^{n+1} of \overrightarrow{D}^{n+1}, therefore is the inclusion morphism we expect. We now have to check that Glob(ϕ_{α}) is a correct attaching map for globular CW-complexes. For (x, u) ∈ Glob(S^{n−1}) (x ∈ S^{n−1}, u ∈ \overrightarrow{I}), we have Glob(ϕ_{α})(x, u) = (ϕ_{α}(x), u). We have to see that it is non-decreasing. Let (x, u) and (x′, u′) be two elements of Glob(S^{n−1}) such that (x, u) ⩽ (x′, u′). We have the following cases:

• u = 0 then Glob(ϕ_{α})(x, u) = \underline{ι}, thus is less or equal than Glob(ϕ_{α})(x′, u′),

• u′ = 1 then Glob(ϕ_{α})(x′, u′) = \underline{σ}, thus is greater or equal than Glob(ϕ_{α})(x, u),

• 0 < u < 1 (the case u = 1 is trivial since it implies u′ = 1, which is the previous case) then u ⩽ u′ and x = x′. Thus, Glob(ϕ_{α})(x, u) = (ϕ_{α}(x), u) ⩽ (ϕ_{α}(x′), u) = Glob(ϕ_{α})(x′, u′).

That Glob(ϕ_{α}) is non-contracting is due to the fact that Glob(ϕ_{α})(\underline{ι}) ≠ Glob(ϕ_{α})(\underline{σ}).

Proposition 2.8. Every globular CW-complex is a CW-complex.

Proof. This is due to the fact that \overrightarrow{e}_{α}^{n} is homeomorphic to e_{α}^{n}.

We end up the section with the Swiss Flag example of Figure 1 described as a globular CW-complex. We will use this example throughout the article to illustrate different constructions and ideas.

Example 2.9. Consider the discrete set SW^{0} = {0, 1, 2, 3, 4, 5} × {0, 1, 2, 3, 4, 5}. Let

S = {((i, j), (i + 1, j)) for (i, j) ∈ {0, …, 4} × {0, …, 5}}
∪ {((i, j), (i, j + 1)) for (i, j) ∈ {0, …, 5} × {0, …, 4}}
\ ({((2, 2), (2, 3)), ((2, 2), (3, 2)), ((2, 3), (3, 3)), ((3, 2), (3, 3))})

The globular CW-complex SW^{1} is obtained from SW^{0} by attaching a copy of \overrightarrow{D}^{1} to each pair (x, y) ∈ S with x ∈ SW^{0} identified with \underline{ι} and y ∈ SW^{0} identified with \underline{σ}. The globular CW-complex SW^{2} is obtained from SW^{1} by attaching to each square ((i, j), (i + 1, j + 1)) except (i, j) ∈ {(2, 1), (1, 2), (2, 2), (3, 2), (2, 3)} a globular cell \overrightarrow{D}^{2} such that each execution path ((i, j), (i + 1, j), (i + 1, j + 1)) and ((i, j), (i, j + 1), (i+1, j +1)) is identified with one of the execution path of \overrightarrow{S}^{1} (there is no unique

Figure 5: Running example of globular CW-complex

choice to do that). Let SW = SW^{2} (cf. Figure 5 where the bold dots represent the points of the 0-skeleton).

2.4. Morphism of globular CW-complexes Definition 2.10. The category glCW of globular CW-complexes is the category having as objects the globular CW-complexes and as morphisms the continuous maps f : X ⟶ Y satisfying the two following properties :

• f(X^{0}) ⊂ Y^{0}

• for every non-constant execution path ϕ of X, f ∘ ϕ must not only be an execution path (f must preserve partial order), but also f ∘ ϕ must be nonconstant as well : we say that f must be non-contracting.

The condition of non-contractibility is very analogous to the notion of noncontracting ω-functors appearing in [12]. Notice also that the attaching maps in the definition of a globular CW-complex are morphisms in glCW. This non-contractibility condition will be justified in Section 6.

A non-constant execution path of a globular CW-complex X induces a morphism of globular CW-complexes from \overrightarrow{I} to X.

Proposition 2.11. The functor Glob(−) induces a functor still denoted by Glob(−) from the category CW of CW-complexes to the category glCW of globular CWcomplexes.

Proof. It is an immediate consequence of Proposition 2.7.

Figure 6: Another example of globular CW-complex

Example 2.12. As example of morphisms of globular CW-complexes, the identity map of [0, 5]×[0, 5] induces a morphism of globular CW-complexes from the globular CW-complex of Figure 6 to that of Figure 5. It will be an example of T-homotopy equivalence (Section 4.2).

3. Relation with other formalizations

3.1. Gluing closed partial orderings

Let us remind some definitions to fix the notations. The category of Hausdorff topological spaces with the continuous maps as morphisms will be denoted by Haus. The category of general topological spaces without further assumption will be denoted by Top.

Let (X, R) be a global po-space. We say that (U, ⩽) is a sub-po-space of (X, R) if and only if it is a po-space such that U is a topological subspace of X and such that ⩽ is the restriction of R to U.

Let X be a Hausdorff topological space. A collection U(X) of po-spaces (U, ⩽_{U}) covering X is called a local po-structure if for every x ∈ X, there exists a po-space (W (x), ⩽_{W (x)}) such that:

• W (x) is an open neighborhood containing x,

• the restrictions of ⩽_{U} and ⩽_{W (x)} to W (x) ∩ U coincide for all U ∈ U(X) such that x ∈ U. This can be stated as: y ⩽_{U} z if and only if y ⩽_{W (x)} z for all U ∈ U(X) such that x ∈ U and for all y, z ∈ W (x) ∩ U. Sometimes, W (x) will be denoted by W_{X}(x) to avoid ambiguities. Such a W_{X}(x) is called a po-neighborhood.

Two local po-structures are equivalent if their union is a local po-structure. This defines an equivalence relation on the set of local partial structures of X. A topological space together with an equivalence class of local po-structures is called a local po-space [6]. Notice that a global po-space is a local po-space.

A morphism f of local po-spaces (or dimap) from (X, U) to (Y, V) is a continuous map from X to Y such that for every x ∈ X,

• there is a po-neighborhood W (f(x)) of f(x) in Y,

• there exists a po-neighborhood W (x) of x in X with W (x) ⊂ f^{−1}(W (f(x))),

• for y, z ∈ W (x), y ⩽ z implies f(y) ⩽ f(z).

In particular, a dimap f from a po-space X to a po-space Y is a continuous map from X to Y such that for any y, z ∈ X, y ⩽ z implies f(y) ⩽ f(z). A morphism f of local po-spaces from [0, 1] endowed with the usual ordering (denoted by \overrightarrow{I}) to a local po-space X is called dipath or sometime execution path.

The category of Hausdorff local po-spaces with the dimaps as morphisms will be denoted by LPoHaus. The mapping Glob(−) of Proposition 2.3 yields a functor from Haus to LPoHaus.

3.2. Globular CW-complex and local po-space We now relate globular CW-complexes with local po-spaces.

3.2.0.1. Convention In the sequel, for any X and Y two topological spaces, we endow the disjoint sum X ⊔ Y with the final topology induced by both inclusion maps X ⊂ X ⊔ Y and Y ⊂ X ⊔ Y.

Both following lemmas summarize well-known facts about topological spaces : see [28] exercises 8.12 and 8.13.

Lemma 3.1. Let ϕ be a closed continuous map from X to Y and let Z ⊂ Y. Let U be an open subset of X containing ϕ^{−1}(Z). Then there exists an open subset V of Y such that Z ⊂ V and ϕ^{−1}(V) ⊂ U.

Lemma 3.2. Let A be a closed subset of X. Let f be a continuous map from A to Y. Consider the quotient topological space X ⊔_{f} Y := (X ⊔ Y)/ ∼ where ∼ is the equivalence relation on X ⊔ Y generated by {(a, f(a)) ∈ (X ⊔ Y) × (X ⊔ Y), a ∈ A}. Let ϕ be the canonical continuous map from X ⊔ Y to X ⊔_{f} Y. Then

1. A subset Ω of X ⊔_{f} Y is open (resp. closed) in X ⊔_{f} Y if and only if ϕ^{−1}(Ω)∩X is open (resp. closed) in X and ϕ^{−1}(Ω) ∩ Y is open (resp. closed) in Y.

2. As soon as A is a closed subset of X, X − A can be identified to the open subset ϕ(X − A) of X ⊔_{f} Y and Y can be identified to the closed subset ϕ(Y) of X ⊔_{f} Y.

3. If f(A) is a closed subset of Y, then Y − f(A) can be identified to the open subset ϕ(Y − f(A)) of X ⊔_{f} Y and f(A) to the closed subset ϕ(f(A)) of Y.

4. If A is compact, then ϕ is a closed map.

5. If A is compact and if X and Y are Hausdorff, then X ⊔_{f} Y is Hausdorff.

Theorem 3.3. Every globular CW-complex X is a local po-space.

Proof. We prove that attaching globular n-cells to any locally compact local pospace still defines a local po-space. As points are trivial local po-spaces, the theorem will follow from an easy induction.

First we say that a local po-structure is small if for all U and V in the open covering defining the local po-structure, ⩽_{U} and ⩽_{V} coincide on U ∩ V. It is easy to see that all local po-spaces X admit (in its equivalence class of coverings) a small local po-structure : if W_{X}(x) is a po-neighborhood, then any subset of W_{X}(x) which is a neighborhood of x is also a po-neighborhood ; hence one can assume that W (x) ⊂ U for some U ∈ U and hence that the partial order on W_{X}(x) is induced from U. The po-neighborhoods satisfying this extra condition are called small poneighborhoods and they give a neighborhood basis for the topology on X, since the intersection of two small po-neighborhoods are again a small po-neighborhood. Moreover, the covering by the small po-neighborhoods defines the local partial order.

Let X be a local po-space: it is defined by a covering (U, (⩽_{U})_{U∈U}) of open sub-po-spaces of X together with (W_{X}(x), ⩽_{W_{X}(x)}), for all x ∈ X, the local neighborhood and the corresponding partial order. We now only consider any of its small representatives in its equivalence class of local po-structures (we still call X = (U, (⩽_{U})_{U∈U})). \overrightarrow{D}^{n} is a local po-space, which is actually a (global) po-space. So its covering is (\overrightarrow{D}^{n}, ⩽\overrightarrow{D}_{n}) with corresponding (W\overrightarrow{D}_{n}(x) = \overrightarrow{D}^{n}, ⩽_{W\overrightarrow{D}_{n} (x)}=⩽\overrightarrow{D}_{n}).

Let f : \overrightarrow{S}^{n−1} ⟶ X be an attaching map^{5} of a globular n-cell \overrightarrow{e}^{n}. We construct the topological space Z = \overrightarrow{D}^{n} ⊔_{f} X as defined by Lemma 3.2. Let Φ : \overrightarrow{D}^{n} ⊔ X → \overrightarrow{D}^{n} ⊔_{f} X be the canonical surjective map. We have a commutative diagram in the category of topological spaces:

[figure: \overrightarrow{S}^{n−1}; f; X; \overrightarrow{D}^{n}; i; Φ_{2}; Z; Φ_{1}]

where i is the inclusion map and Φ_{1}, Φ_{2} are defined by the push-out diagram. Of course, Φ_{1} is injective since i is injective. We identify Φ_{1} with Φ restricted to X and also identify Φ_{2} with Φ since it is the composition of the inclusion map from\overrightarrow{D}^{n} to \overrightarrow{D}^{n} ⊔ X with Φ.

As \overrightarrow{S}^{n−1} is compact, by Lemma 3.2, point 3 and 4, we know that Φ is a closed map and Z is Hausdorff (this holds true by induction again). Therefore f(\overrightarrow{S}^{n−1}) is closed since it is compact. Thus by point 3 of Lemma 3.2, X\\overrightarrow{S}^{n−1} can be identified with the open subset Φ(X\f(\overrightarrow{S}^{n−1})) of Z and f(\overrightarrow{S}^{n−1}) with the closed subset Φ(f(\overrightarrow{S}^{n−1})) of Z.

Similarly, \overrightarrow{S}^{n−1} is a closed subset of \overrightarrow{D}^{n} so by point 2 of Lemma 3.2, \overrightarrow{D}^{n}\f(\overrightarrow{S}^{n−1})

5We consider one attaching map at a time only, the argument easily transposes to any number of attaching maps.

Figure 7: First case for the definition of (U_{z}, ≺_{U_{z}}).

can be identified with the open subset Φ(\overrightarrow{D}^{n}\f(\overrightarrow{S}^{n−1})) of Z and X can be identified with the closed subset Φ(X) of Z. We use these identifications below.

Take now z ∈ Z; we are going to construct a neighborhood U_{z} of z in Z together with a local po-structure on U_{z}, making Z into a local po-space with the local po-structure (U_{z}, ≺_{U_{z}})_{z∈Z} :

(1) Suppose z ∈ \overrightarrow{D}^{n}\f(\overrightarrow{S}^{n−1}) (see Figure 7). We define U_{z} = \overrightarrow{D}^{n}\f(\overrightarrow{S}^{n−1}) that we noticed is identified with an open subset of Z, and a binary relation ≺_{U_{z}} on U_{z} such that u ≺_{U_{z}} v if u ⩽\overrightarrow{D}_{n} v. ≺_{U_{z}} is obviously a partial order.

(2) Suppose z ∈ X\f(\overrightarrow{S}^{n−1}) (see Figure 8). We have noticed that X\f(\overrightarrow{S}^{n−1}) can be identified with an open subset of Z. W_{X}(z) is an open subset of \overrightarrow{D}^{n}⊔X containing Φ^{−1}({z}) = {z} since z is in X and Φ is injective on this part. Therefore, by Lemma 3.1, there exists U_{z} open of Z containing {z} such that Φ^{−1}(U_{z}) ⊆ W_{X}(z). We define the partial ordering ≺_{U_{z}} to be the same as ⩽_{W_{X}(z)} on U_{z}.

(3) The only remaining possibility is that z ∈ f(\overrightarrow{S}^{n−1}) (see Figure 10). Let us first subdivide the segment [0, 1]; take six elements of ]0, 1[ 0 < a < b < c < d < e < f < 1. We let (see Figure 9),

– F_{1} = [e, 1] ∪ [0, b], with partial order ⩽_{F_{1}} defined by, for x ∈ [e, 1] and y ∈ [e, 1] or x ∈ [0, b] and y ∈ [0, b], it is the usual partial order induced by [0, 1] and for x ∈ [e, 1] and y ∈ [0, b], x ⩽_{F_{1}} y.

– F_{2} = [a, d], with the usual partial order.

– F_{3} = [c, f], with the usual partial order.

We notice that if we identify 0 with 1, (F_{1}^{∘}, ⩽_{F_{1}}), (F_{2}^{∘}, ⩽_{F_{2}}) and (F_{3}^{∘}, ⩽_{F_{3}}) is a small local po-structure on the circle and the canonical surjection from the po-space \overrightarrow{I} to this local po-space is a morphism of local po-spaces. We define \overrightarrow{D}_{i}^{n} = \{(x, t) | x ∈ D^{n−1}, t ∈ F_{i}\} (similarly \overrightarrow{S}_{i}^{n−1} = \{(x, t) | x ∈ S^{n−2}, t ∈ F_{i}\}) closed subset of \overrightarrow{D}^{n}. The partial orders ⩽_{F_{i}} induce partial Homology, Homotopy and Applications, vol. 5(2), 2003 54

Figure 8: Second case for the definition of (U_{z}, ≺_{U_{z}}).

Figure 9: The subdivision of an oriented circle.

Figure 10: Third case for the definition of (U_{z}, ≺_{U_{z}}).

orders ⩽\overrightarrow{D}_{n}_{i} on \overrightarrow{D}_{i}^{n}. As X is locally compact, we can find W_{z} a closed neighborhood of z contained in W_{X}(z). Consider the composite map Φ_{i}:

\xymatrix{\overrightarrow{D}_{i}^{n} ⊔ W_{z} \ar[dr]_{Φ_{i}} \ar[r]^{⊆} & \overrightarrow{D}^{n} ⊔ X \ar[d]_{Φ} \\  & \overrightarrow{D}^{n} ⊔_{f} X}

It is a closed continuous map as a composition of two closed continuous maps. There exists (a non-necessarily unique) (w, t) ∈ S^{n−2} × \overrightarrow{I} such that f(w, t) =

z. Necessarily, t belongs to some F_{i_{z}}^{∘}. We have

Φ_{i_{z}}^{−1}(\{z\}) ⊆ \overrightarrow{D}_{i_{z}}^{n} ⊔ W_{z}

thus by Lemma 3.1 there exists an open neighborhood U_{z} of z such that

Φ_{i_{z}}^{−1}(U_{z}) ⊆ \overrightarrow{D}_{i_{z}}^{n} ⊔ W_{z}

Let U_{z}^{X} be the subset U_{z} ∩ Φ(X) of Z and U_{z}^{D} be the subset U_{z} ∩ (Φ(\overrightarrow{D}^{n}\f(\overrightarrow{S}^{n−1}))) of Z. This is a partition of U_{z}. Notice that we can identify elements of U_{z}^{D} with elements of \overrightarrow{D}^{n}\\overrightarrow{S}^{n−1} and elements of U_{z}^{X} with elements of X. By construction, U_{z}^{D} ⊆ \overrightarrow{D}_{i_{z}}^{n}\\overrightarrow{S}_{i_{z}}^{n−1}. We now define a binary relation ≺_{U_{z}} on U_{z} as follows:

– for u, v ∈ U_{z}^{X}, u ≺_{U_{z}} v if u ⩽_{W_{X}(z)} v,

– for u, v ∈ U_{z}^{D}, u ≺_{U_{z}} v if u ⩽\overrightarrow{D}{n \atop iz} v,

– for u ∈ U_{z}^{X} and v ∈ U_{z}^{D}, ∗ if i_{z} = 1, u ≺_{U_{z}} v if u ⩽_{W_{X}(z)} f(\underline{ι}) and 0 < t(v) < a, (t(v) is the

unique parameter in F_{1} such that v = (w, t(v)) for some w),

∗ if i_{z} = 2, u ≺_{U_{z}} v if u ⩽_{W_{X}(z)} f(\underline{ι}),

∗ if i_{z} = 3 we can never have u ≺_{U_{z}} v.

– for u ∈ U_{z}^{D} and v ∈ U_{z}^{X}, ∗ if i_{z} = 1, u ≺_{U_{z}} v if f(\underline{σ}) ⩽_{W_{X}(z)} v and b < t(u) < 1,

∗ if i_{z} = 2 we can never have u ≺_{U_{z}} v,

∗ if i_{z} = 3, u ≺_{U_{z}} v if f(\underline{σ}) ⩽_{W_{X}(z)} v. This defines a partial order indeed. Reflexivity and transitivity are obvious. We now check antisymmetry. Let u and v be two elements of U_{z} such that u ≺_{U_{z}} v and v ≺_{U_{z}} u. If u and v both belong to U_{z}^{X} or U_{z}^{D} it is obvious that this implies u = v, since the relation ≺_{U_{z}} coincide with one of the partial orders ⩽_{W_{X}(z)} or ⩽\overrightarrow{D}_{n}_{i} in that case. Suppose u ∈ U_{z}^{X}, v ∈ U_{z}^{D} with,

– i_{z} = 1, we have by definition u ⩽_{W_{X}(z)} f(\underline{ι}) and 0 < t(v) < b and

f(\underline{σ}) ⩽_{W_{X}(z)} u and e < t(v) < 1, which is of course impossible,

– i_{z} = 2, v ≺_{U_{z}} u is impossible by definition,

– i_{z} = 3, u ≺_{U_{z}} v is impossible by definition. It follows that (U_{z}, ≺_{U_{z}})_{z∈Z} defines a small local po-structure since by construc-

tion, for z ≠ z′, the partial orders ≺_{U_{z}} and ≺_{U_{z′}} coincide on the intersection U_{z} ∩U_{z′} (if non-empty). It then suffices to set W_{Z}(z) := U_{z}.

Theorem 3.4. The previous embedding induces a functor from the category of globular CW-complexes to that of local po-spaces.

Proof. Let X and Y be two globular CW-complexes and f : X → Y be a morphism of CW-complexes. The globular cellular decomposition of X yields a set of characteristic maps ϕ_{α} : \overrightarrow{D}^{n_{α}} → X satisfying :

1. The mapping ϕ_{α} ↾_{\overrightarrow{D}^{nα} −\overrightarrow{S}^{nα−1}} induces an homeomorphism from \overrightarrow{e}^{n_{α}} to its image.

2. All the previous globular cells are disjoint and their union gives back X.

3. A subset of X is closed if and only if it meets the closure of each globular cells

of X in a closed set. where α runs over a well-ordered set of indexes κ (one can suppose that κ is a finite or transfinite cardinal). One can suppose that the mapping α ↦ n_{α} is nondecreasing. Let X^{[−1]} = ∅. Let β be an ordinal with β ⩽ κ. If β is a limit ordinal, let X^{[β]} = \underrightarrow{lim}_{α<β} X^{[α]}. If β = γ + 1 for some ordinal γ, then let X^{[β]} = \overrightarrow{D}^{n_{β}} ⊔_{ϕ_{β}} X^{[γ]}.

Notice that X^{[γ]} is closed in X^{[β]}.

We are going to prove by transfinite induction on β the statement P (β) : For any globular CW-complex X and for any set of characteristic maps ϕ_{α} : \overrightarrow{D}^{n_{α}} → X as above, a morphism of globular CW-complexes from X to Y induces a morphism of local po-spaces from X^{[β]} to Y.

Necessarily the equality n_{0} = 0 holds therefore P (0) is true. Now let us suppose that P (α) holds for α < β and some β ⩾ 1. We want to check that P (β) then holds as well. If β = 1, then X^{[β]} is either the two-point discrete space, or a loop. So P (1) holds. So let us suppose β ⩾ 2.

There are two mutually exclusive cases :

1. The case where β is a limit ordinal. Let x ∈ X^{[β]}. Then x ∈ X^{[α]} for some α < β and the induction hypothesis can be applied ; the result follows from the fact that the direct limit is endowed with the weak topology.

2. The case where β = γ + 1 for some cardinal γ. Then X^{[β]} = \overrightarrow{D}^{n_{β}} ⊔_{ϕ_{β}} X^{[γ]} with the above notations. With the notation and identification as in the proof of Theorem 3.3, one has three mutually exclusive cases :

• x ∈ X^{[γ]}\ϕ_{β}(\overrightarrow{S}^{n_{β}−1}) : in this case, the induction hypothesis can be applied ;

• x ∈ \overrightarrow{D}^{n_{β}}\ϕ_{β}(\overrightarrow{S}^{n_{β}−1}) : let W_{Y} (f(x)) be a po-neighborhood of f(x) in Y ; then f^{−1}(W_{Y} (f(x))) is an open of \overrightarrow{D}^{n_{β}} ; there exists a basis of \overrightarrow{D}^{n_{β}} by global po-spaces so there exists a po-neighborhood W_{x} of x in \overrightarrow{D}^{n_{β}} such that W_{x} ⊂ f^{−1}(W_{Y} (f(x))) ;

• x ∈ ϕ_{β}(\overrightarrow{S}^{n_{β}−1}) : let Φ_{β} be the canonical closed map from \overrightarrow{D}^{n_{β}} ⊔ X^{[γ]} to X^{[β]} ; by induction hypothesis, f ∘ Φ_{β} ↾_{X^{[γ]}}: X^{[γ]} → Y is a morphism of po-spaces ; therefore there exists a po-neighborhood W_{f(x)} of f(x) in Y and a po-neighborhood W_{x} of x in X^{[γ]} such that

W_{x} ⊂ (f ∘ Φ_{β} ↾_{X^{[γ]}})^{−1} (W_{f(x)})

So (Φ_{β})^{−1}(\{x\}) ∈ \overrightarrow{D}^{n_{β}} ⊔ W_{x} and by Lemma 3.1, there exists an open V_{x} of X^{[γ]} such that (Φ_{β})^{−1}(V_{x}) ∈ \overrightarrow{D}^{n_{β}} ⊔ W_{x}. Then let us considering the U_{x} of the proof of Theorem 3.3. Since f is continuous, f^{−1}(W_{f(x)}) is open and

∅ ≠ V_{x} ∩ U_{x} ∩ f^{−1}(W_{f(x)}) ⊂ f^{−1}(W_{f(x)})

We now prove an interesting tool for constructing globular complexes.

Theorem 3.5. Let Z be a compact local po-space, let Y be a closed subset of Z, and let \overrightarrow{e} be a globular n-cell in Z with \overrightarrow{e} ∩ Y = ∅. Suppose there exists a relative isomorphism^{6} of globular CW-complexes \xymatrix{Φ : (\overrightarrow{D}^{n}, \overrightarrow{S}^{n−1}) \ar[r] & (\overrightarrow{e} ∪ Y, Y)}. Set f =

Φ|\overrightarrow{S}^{n−1}. then the obvious map (induced by Φ and by Id_{Y})

Ψ : \xymatrix{Y_{f} = \overrightarrow{D}^{n} ⊔_{f} Y \ar[r] & \overrightarrow{e} ∪ Y}

is an isomorphism of local po-spaces.

Proof. The map Ψ is clearly bijective. Let g be the canonical map from \overrightarrow{D}^{n} ⊔ Y to \overrightarrow{D}^{n} ⊔_{f} Y and let Ω be an open subset of \overrightarrow{e} ∪ Y. Then g^{−1}Ψ^{−1}(Ω) = Φ^{−1}(Ω ∩

6Meaning that Φ is an isomorphism of globular CW-complexes from \overrightarrow{D}^{n} to \overrightarrow{e} ∪ Y such that it restricts to an isomorphism of globular CW-complexes from \overrightarrow{S}^{n−1} ⊆ \overrightarrow{D}^{n} to Y ⊆ \overrightarrow{e} ∪ Y.

\overrightarrow{e}) ⊔ (Ω ∩ Y) is an open subset of \overrightarrow{D}^{n} ⊔ Y, therefore Ψ is continuous. So \overrightarrow{e} ∪ Y is compact and therefore Ψ is an homeomorphism. The fact that Ψ preserves the structure of local po-spaces is obvious.

3.3. Globular CW-complex and precubical set

We are going to show that in fact, there is a geometric realization functor (which should be homotopically equivalent to the former one composed with the realization of precubical sets as local po-spaces of [6] in some sense) transforming a precubical set into a globular CW-complex. We first need a few (classical) remarks.

Definition 3.6. [2] [22] A precubical set (or HDA) consists of a family of sets

(M_{n})_{n⩾0} and of a family of face maps \xymatrix{M_{n} \ar[r]^{∂_{i}^{α}} & M_{n−1}} for α ∈ \{0, 1\} and 1 ⩽ i ⩽ n which satisfies the following axiom (called sometime the cube axiom) :

∂_{i}^{α}∂_{j}^{β} = ∂_{j−1}^{β}∂_{i}^{α} for all 1 ⩽ i < j ⩽ n and α, β ∈ {0, 1}.

If M is a precubical set, the elements of M_{n} are called the n-cubes. An element of M_{n} is of dimension n. The elements of M_{0} (resp. M_{1}) can be called the vertices (resp. the arrows) of K.

Let M and N be two HDA, and f a family f_{n} : M_{n} → N_{n} of functions. The family f is a morphism of HDA if and only if f_{n} ∘ ∂_{i}^{α} = ∂_{i}^{α} ∘ f_{n+1} for all n ∈ ℕ and 0 ⩽ i ⩽ n. HDA together with these morphisms form a category which we denote by □Set. Conventionally, this category can be identified with the set-valued pre-sheaves of some small finite free category □, and therefore it is cocomplete.

The small category □ can be described as a category whose objects are [n], where n ∈ ℕ and whose morphisms are generated by,

[n − 1] [figure: δ_{i}^{0}; δ_{j}^{1}] [n]

with 1 ⩽ i, j ⩽ n and satisfying the opposite of the cube axiom, i.e. δ_{j}^{β}δ_{i}^{α} = δ_{i}^{α}δ_{j−1}^{β} for all 1 ⩽ i < j ⩽ n and α, β ∈ {0, 1}.

There is a truncation functor T_{n} : □Set → □Set defined by, T_{n}(M)_{m} = M_{m} if m ⩽ n and T_{n}(M)_{m} = ∅ if m > n.

Now, let D_{[n]} be the representable functor from □ to Set with D_{[n]}([p]) = □Set([p], [n]). We define the singular n-cubes of a HDA M to be any morphism σ : D_{[n]} → M.

Lemma 3.7. The set of singular n-cubes of a HDA M is in one-to-one correspondence with M_{n}. The unique singular n-cube corresponding to a n-cube x ∈ M_{n} is denoted by σ_{x} : D_{[n]} → M. It is the unique singular n-cube σ such that σ(Id_{[n]}) = x.

Proof. The proof goes by Yoneda’s lemma.

There is only one morphism in □ from a given [n] to itself, the identity of [n], hence D_{[n]}\{Id} is a functor which has only as non-empty values the D_{[n]}([p]) with p < n (“it is of dimension n − 1”). We write ∂D_{[n]} for this functor. For σ a natural transformation from D_{[n]} to M, we write ∂σ for its restriction to ∂D_{[n]}.

Proposition 3.8. Let M be a HDA. The following diagram is co-cartesian (for n ∈ ℕ),

[figure: ∐_{x∈M_{n+1}} ∂D_{[n+1]}; ⨆_{x∈M_{n+1}} ∂σ_{x}; T_{n}(M); ∐_{x∈M_{n+1}} D_{[n+1]}; ⊆; ⨆_{x∈M_{n+1}} σ_{x}; T_{n+1}(M); ⊆]

where ∂D_{[n+1]} = T_{n}(D_{[n+1]}) and ∂σ_{x} = σ_{x}_{|∂D_{[n+1]}}.

Proof. We mimic the proof of [8]: it suffices to prove that the diagram below (in the category of sets) is cocartesian for all p ⩽ n + 1,

[figure: ∐_{x∈M_{n+1}}(∂D_{[n+1]})_{p}; ⨆_{x∈M_{n+1}} (∂σ_{x})_{p}; (T_{n}(M))_{p}; ∐_{x∈M_{n+1}}(D_{[n+1]})_{p}; ⊆; ⨆_{x∈M_{n+1}} (σ_{x})_{p}; (T_{n+1}(M))_{p}; ⊆]

since colimits (hence push-outs) are taken point-wise in a functor category into Set.

For all p < n + 1, the inclusions are in fact bijections, and the diagram is then obviously cocartesian.

For p = n + 1, the complement of ⨆_{x∈M_{n+1}}(∂D_{[n+1]})_{p} in ⨆_{x∈M_{n+1}}(D_{[n+1]})_{p} is the set of copies of cubes Id_{[n+1]}, one for each cube of M_{n+1}. This means that the map ⨆_{x∈M_{n+1}}(σ_{x})_{p} induces a bijection from the complement of ⨆_{x∈M_{n+1}}(∂D_{[n+1]})_{p} onto the complement of (T_{n}(M))_{p}. This implies that the diagram is cocartesian for p = n + 1 as well.

This lemma states that the truncation of dimension n+1 of a HDA M is obtained from the truncation of dimension n of M by attaching some standard (n + 1)- cubes D_{[n+1]} along the boundary ∂D_{[n+1]} of (n + 1)-dimensional holes. In fact, any precubical set M is the direct limit of the diagram consisting of all inclusions T_{n−1}(M) ↪ T_{n}(M), hence is also the direct limit of the diagram consisting of all the cocartesian squares above.

We are quite close to the globular CW-complex definition. What we need now is the (classical) notion of geometric realization. Let □_{n} be the standard cube in ℝ^{n} (n ⩾ 0),

□_{n} = {(t_{1}, …, t_{n})|∀i, 0 ⩽ t_{i} ⩽ 1}
□_{0} = {0}

and let δ_{i}^{k} : □_{n−1} → □_{n}, 1 ⩽ i ⩽ n, k = 1, 2, be the continuous functions (n ⩾ 1),

[figure: □_{n}; δ_{i}^{0}; □_{n−1}; □_{n−1}; δ_{i}^{1}]

defined by,

δ_{i}^{k}(t_{1}, …, t_{n−1}) = (t_{1}, …, t_{i−1}, k, t_{i}, …, t_{n−1})

Consider now, for a precubical set M, the set R(M) = ⨆_{n} M_{n} × □_{n}. The sets M_{n} have the discrete topology and □_{n} is endowed with the topology induced as a subset of ℝ^{n} with the standard topology thus R(M) is a topological space with the disjoint sum topology. Let ≡ be the equivalence relation induced by the identities:

∀k, i, n, ∀x ∈ M_{n+1}, ∀t ∈ □_{n}, n ⩾ 0, (∂_{i}^{k}(x), t) ≡ (x, δ_{i}^{k}(t))

Let |M| = R(M)/ ≡ have the quotient topology. The topological space |M| is called the geometric realization of M. This actually yields a functor from □Set to Top by setting for f : X → Y a morphism in □Set, R(f) : R(X) ⟶ R(Y) by: R(f)((x, t)) = (f(x), t). This functor commutes with colimits since it is a left adjoint functor (the right adjoint being a singular cube functor, see [6]).

Thus, the geometric realization of a precubical set M is the direct limit of the diagram:

[figure: ∐_{x∈M_{n+1}} ∂□_{n+1}; ⨆_{x∈M_{n+1}} |∂σ_{x}|; |T_{n}(M)|; ∐_{x∈M_{n+1}} □_{n+1}; ⊆; ⨆_{x∈M_{n+1}} |σ_{x}|; |T_{n+1}(M)|; ⊆]

since it is easily shown that, • |D_{[n+1]}| is homeomorphic to □_{n+1},

• the inclusion of ∂D_{[n+1]} into D_{[n+1]} induces an homeomorphism between

|∂D_{[n+1]}| onto the boundary ∂□_{n+1} of the standard (n + 1)-cube. Obviously, each σ_{x} induces a homeomorphism from ∂□_{n+1} onto a connected component of |T_{n+1}(M)|\|T_{n}(M)|, which is homeomorphic to the interior of an (n + 1)- cube, and to e^{n+1}. This shows that at least, |M| is a CW-complex. We are now going to show that this direct limit can be slightly transformed so as to produce a globular CW-complex.

Let C_{t} = {(t_{1}, …, t_{n}) ∈ □_{n}|t_{1} + ⋯ + t_{n} = t}, 0 ⩽ t ⩽ n. As the intersection of □_{n} with a hyperplane, C_{t} is a convex polyhedron. It is spanned by (the convex hull of) extremal points all of whose coordinates but one are either 0 or 1. More precisely, extremal points have ⌊t⌋ 1-coordinates, (n − ⌊t⌋ − 1) 0-coordinates and a single coordinate is given by t − ⌊t⌋. (⌊ ⌋ denotes Gauss brackets, i.e., ⌊t⌋ is the largest integer ⩽ t.)^{7} In particular, the point (\frac{t}{n}, …, \frac{t}{n}) is an interior point in C_{t} for 0 < t < n. For t = 0 and for t = n, the polyhedron C_{t} degenerates to a single point.

Let h : R^{n} → R^{n−1} denote the linear map given by

h(t_{1}, …, t_{n}) = (t_{2} − \frac{t_{1} + ⋯ + t_{n}}{n} , …, t_{n} − \frac{t_{1} + ⋯ + t_{n}}{n}).

7This generalizes the picture in dimension 3, where C_{t} is either a triangle or a hexagon (for 1 < t < 2).

Its kernel ker(h) is equal to the diagonal Δ ⊂ R^{n}. Let D_{t} = h(C_{t}) ⊂ R^{n−1}, 0 ⩽ t ⩽ n. As the image of a convex polyhedron under an injective affine map (on the hyperplane ∑ t_{i} = t), D_{t} is itself a convex polyhedron containing the origin 0 = h(\frac{t}{n}, …, \frac{t}{n}) in its interior for 0 < t < n; D_{t} degenerates to a single point exactly for t = 0 and t = n.

Define m : □_{n}\Δ → R by m(t_{1}, …, t_{n}) = min_{i} max\{m_{i} ⩾ 0| 0 ⩽ \frac{t}{n}+m_{i}(t_{i}−\frac{t}{n}) ⩽ 1}. (m is continuous, but not well-defined on the diagonal Δ ⊂ □_{n}; on the ray from the diagonal point in C_{t} through t = (t_{1}, …, t_{n}) to the boundary of C_{t}, the number \frac{1}{m(t)} measures the ratio of the segment between the diagonal and t). A homeomorphism H : □_{n} → Glob(D^{n−1}) can be defined as the composition of the quotient map q : I × D^{n−1} → Glob(D^{n−1}) with the following map H̄ : □_{n} → I × D^{n−1}:

H̄(t_{1}, …, t_{n}) = \{ \begin{matrix}(\frac{t_{1}+···+t_{n}}{n} , \frac{h(t_{1},...,t_{n})}{m(t_{1},...,t_{n})||h(t_{1},...,t_{n})||}) & (t_{1}, …, t_{n}) ∉ Δ, \\ (\frac{t_{1}+···+t_{n}}{n} , 0, …, 0) & (t_{1}, …, t_{n}) ∈ Δ. \end{matrix}

The function m ≡ 1 on ∂□_{n} \ {0, 1}, whence H(∂□_{n} \ {0, 1}) = int(I) × S^{n−2} and H(□_{n} \ {0, 1}) = int(I) × D^{n−1}. The restriction of H̄ to □_{n} \ {0, 1} is a continuous bijection onto its image. Remark, that H – but not H̄ – is continuous in the corners points, (0, …, 0) and (1, … 1). As a continuous bijection from the compact space □_{n} into the Hausdorff space Glob(D^{n−1}), the map H is a homeomorphism.

Define a partial order on □_{n} by x ⩽_{gl} y if and only if H(x) ⩽ H(y) (using the partial order on Glob(D^{n−1})). Then by definition, (□_{n}, ⩽_{gl}) is isomorphic as a pospace to \overrightarrow{D}^{n} (through H). Notice also that H^{−1}(∂\overrightarrow{D}^{n}) = ∂□_{n}. We are now ready for the construction of a globular CW-complex out of M.

• We start with X^{0} = ∐_{x∈M_{0}} □_{0}.

• We form inductively the n-skeleton X^{n} from X^{n−1}, that we prove (again by induction on n) to be homeomorphic to |T_{n−1}(M)|, by attaching globular ncells \overrightarrow{e}_{σ_{x}}^{n} via maps ϕ_{σ_{x}} : \overrightarrow{S}^{n−1} ⟶ X^{n−1}, where σ_{x} is any singular n-cube of M. The attaching map is defined as the composite:

[figure: ϕ_{σ_{x}} :; \overrightarrow{S}^{n−1}; H^{−1}; ∂□_{n}; |∂σ_{x}|; |T_{n−1}(M)| ∼ X^{n−1}]

What will remain to be shown is that this is non-decreasing and non-contracting.

• X = ⋃_{n} X^{n} with the weak topology (the direct limit of the diagram composed of the attaching maps).

We now check that the attaching maps are non-decreasing and non-contracting. First of all, for any x ∈ M_{n}, we consider σ_{x} : D_{[n]} → M, the unique morphism of precubical sets such that σ(Id_{D_{[n]}}) = x ∈ M_{n}. We have to check that if y ⩽_{gl} z in (Id_{D_{[n]}}, ∂□_{n}), then |σ_{x}|(x) ⩽_{gl} |σ_{x}|(z) in (x, □_{n}) ∈ M. All points of |D_{[n]}| have a representative in (Id_{D_{[n]}}, □_{n}), i.e. can be written as (Id_{D_{[n]}}, t_{1}, ⋯, t_{n}) with 0 ⩽ t_{i} ⩽ 1 (for all i, 1 ⩽ i ⩽ n). Now, |σ_{x}|(Id_{D_{[n]}}, t_{1}, ⋯, t_{n}) = (x, t_{1}, ⋯, t_{n}), hence |σ_{x}| preserves trivially the partial order ⩽_{gl} of □_{n}, hence |σ_{x}| ∘ H^{−1} preserves it as well. Since H^{−1}(∂\overrightarrow{D}^{n}) = ∂□_{n}, ∂σ_{x} also preserves ⩽_{gl}.

Now, take an execution path ϕ starting from \underline{ι} (or arriving at \underline{σ}) in \overrightarrow{S}^{n−1}, and suppose that ϕ_{σ_{x}} ∘ ϕ is a constant path of X^{n−1}. Then σ_{x} ∘ H^{−1} ∘ ϕ has constant coordinates in (x, □_{n}) ∈ |T_{n}(M)|, which means, since σ_{x} acts as the identity on these coordinates, that ϕ is a constant path of \overrightarrow{S}^{n−1}. Furthermore, ϕ_{σ_{x}}(\underline{ι}) = σ_{x}(Id_{[n]}, (0, ⋯, 0)) which is also σ_{x}(δ_{0}^{0}d_{1}^{0} ⋯ δ_{n−1}^{0}, □_{0}), so is equal to (δ_{0}^{0}δ_{1}^{0} ⋯ δ_{n−1}^{0}(x), □_{0}) which belongs to T_{n}(M)_{0} = M_{0}. Similarly, ϕ_{α}(\underline{σ}) belongs to X^{0}.

Proposition 3.9. The above construction induces a functor from the category of HDA □Set to the category glCW of globular CW-complexes.

Proof. By definition, a morphism a precubical set sends a n-cube to another ncube. So the realization as globular CW-complexes induce clearly a morphism of glCW.

Example 3.10. Consider the 2-dimensional precubical set sw = (sw_{0}, sw_{1}, sw_{2}) with (front face) boundary maps ∂_{j}^{0} : sw_{i+1} → sw_{i} (i = 0, 1, 0 ⩽ j ⩽ i) and (back face) boundary maps ∂_{j}^{1} : sw_{i+1} → sw_{i} (i = 0, 1, 0 ⩽ j ⩽ i) defined as follows:

• The 0-cubes are sw_{0} = {0, 1, 2, 3, 4, 5} × {0, 1, 2, 3, 4, 5}.

• The 1-cubes are

sw_{1} = {((i, j), (i + 1, j)) for (i, j) ∈ {0, …, 4} × {0, …, 5}}
∪ {((i, j), (i, j + 1)) for (i, j) ∈ {0, …, 5} × {0, …, 4}}
\ ({((2, 2), (2, 3)), ((2, 2), (3, 2)), ((2, 3), (3, 3)), ((3, 2), (3, 3))})

with boundary maps: ∂_{0}^{0}((i, j), (i+1, j)) = (i, j), ∂_{0}^{1}((i, j), (i+1, j)) = (i+1, j).

• The 2-cubes are

sw_{2} = {((i, j), (i + 1, j + 1)) | 0 ⩽ i, j ⩽ 4}
\ {(i, j) ∈ {(2, 1), (1, 2), (2, 2), (3, 2), (2, 3)}

with boundary maps: ∂_{0}^{0}((i, j), (i + 1, j + 1)) = ((i, j), (i + 1, j)), ∂_{1}^{0}((i, j), (i + 1, j + 1)) = ((i, j), (i, j + 1)), ∂_{0}^{1}((i, j), (i + 1, j + 1)) = ((i, j + 1), (i + 1, j + 1)), ∂_{1}^{1}((i, j), (i + 1, j + 1)) = ((i + 1, j), (i + 1, j + 1)).

This precubical set gives the semantics of the term P a.P b.V a.V B | P b.P a.V b.V a as shown in [6]. We see that the realization of this precubical set as defined above is exactly the globular CW-complex of Example 2.9.

3.4. Globular CW-complex and d-space

Marco Grandis defines in [17, 18] a notion of d-space to study the geometry of directed spaces up to a form of dihomotopy. There is a functor which associates to each globular CW-complex X a d-space d_{X} as follows:

• the underlying topological space of d_{X} is the underlying topological space of X, • the set of paths is the union of the space of execution paths of X between any

two points of the 0-skeleton with the set of all points (seen as constant paths). This set of paths is topologized with the Kelleyfication of the compact-open topology (see Section 5.1). The composition operation is the obvious one.

4. Dihomotopy equivalence

As pointed out in [11], there are two types of deformations of HDA which leave unchanged its computer-scientific properties : the spatial ones and the temporal ones. The aim of this section is to define in a precise manner these notions. In other terms, we are going to construct three categories whose isomorphism classes of objects are respectively the globular CW-complexes modulo spatial deformations, modulo temporal deformations and modulo both kinds of deformations together.

We meet in this section a few set-theoretic problems which must be treated carefully. So two universes U and V with U ∈ V are fixed. The sets are the elements of U. One wants to construct categories whose objects are sets and whose the collection of morphisms between any pair of objects is a set as well. So by category, one must understand a V-small category with U-small objects and U-small homsets. By large category, one must understand a category with V-small objects, and V-small homsets whose set of objects is not V-small [1].

4.1. S-homotopy equivalence

Intuitively, the spatial deformations correspond to usual deformations orthogonally to the direction of time. This is precisely what a S-homotopy does.

Definition 4.1. Let f and g be two morphisms from the globular CW-complex X to the globular CW-complex Y. Then f and g are S-homotopic if there exists a continuous map H from X × 𝕀 to Y such that (writing H_{t} = H(−, t)),

• H_{0} = f, H_{1} = g and for any t ∈ [0, 1],

• H_{t} is a morphism of globular CW-complexes from X to Y. When this holds, we write f ∼_{S} g. The map H is called a S-homotopy from f to g. This defines an equivalence relation on the set of morphisms of globular CWcomplexes from X to Y. The quotient set is denoted by [X, Y]_{S}.

For comparison purposes, the set of continuous maps up to homotopy from X to Y will be denoted by [X, Y] and the corresponding equivalence relation by ∼.

If X and Y are two globular CW-complexes, a S-homotopy H : X × 𝕀 → Y without further precisions means that for every t ∈ 𝕀, H_{t} = H(−, t) is a morphism of globular CW-complexes from X to Y and therefore that H is a S-homotopy between H_{0} and H_{1}.

In particular, this means that given x ∈ X^{0}, the image of the map t ↦ H(x, t) is included in the discrete set X^{0}, and therefore that it is the constant map. Therefore, if f and g are two S-homotopic morphisms of globular CW-complexes, then f and g will coincide on the 0-skeleton of X.

The latter remark leads us to introducing the cylinder functor I^{S} associated to the notion of S-homotopy. If X is a CW-complex, let I^{S}Glob(X) := Glob(X × 𝕀).

Now for any globular CW-complex X, let us define I^{S}X inductively on the globular cellular decomposition of X in the following manner :

1) Let I^{S}(X)^{0} := X^{0} ;

2) Let us suppose the n-skeleton I^{S}(X)^{n} defined for n ⩾ 0 ; For every (n + 1)- dimensional globular cell (Glob(D^{n}), ϕ : Glob(S^{n−1}) → X^{n}) of X, the globular CW-complex Glob(D^{n} × 𝕀) is attached to I^{S}(X)^{n} by the attaching map I^{S}ϕ : Glob(S^{n−1} × 𝕀) → I^{S}(X)^{n}.

3) Then the direct limit I^{S}X is a globular CW-complex.

Topologically, I^{S}X is the quotient of X × I by the relations \{x_{0}\} × 𝕀 = \{\overline{x_{0}}\} for every x_{0} ∈ X^{0} (since X^{0} is discrete, this relation is closed and the quotient is then still Hausdorff). Let ϵ_{h} be the morphism from X to I^{S}(X) with ϵ_{h}(x) = (x, h) and σ be the canonical map from X × 𝕀 to I^{S}(X). Then,

Proposition 4.2. Let f and g be two morphisms of globular CW-complexes from X to Y. Then f and g are S-homotopic if and only if there exists a morphism of globular CW-complex \overline{H} from I^{S}(X) to Y such that \overline{H} ∘ ϵ_{0} = f and \overline{H} ∘ ϵ_{1} = g.

Proof. If such a \overline{H} exists, then \overline{H} ∘ σ is a S-homotopy from f to g. Reciprocally, if H is a S-homotopy from f to g, then the map t ↦ H(x_{0}, t) is constant for any x_{0} ∈ X^{0}. Therefore H factorizes by σ, giving the required \overline{H}.

The following proposition gives a simple example of S-homotopic morphisms :

Proposition 4.3. Let X be a CW-complex and consider the globular CW-complex Glob(X) (see Proposition 2.7). Let x ∈ X and consider f_{x} the morphism of globular complexes from \overrightarrow{I} to Glob(X) defined by f_{x}(u) = (x, u). Take x and y two elements that are in the same connected component of X. Then f_{x} and f_{y} are S-homotopic.

Proof. Let γ be a continuous path in X from x to y (X being a CW-complex, its path-connected components coincide with its connected component). Then H(u, t) := (γ(t), u) satisfies the condition of Definition 4.1.

Definition 4.4. Let X be a globular CW-complex. Then two execution paths (see Definition 2.5) γ_{1} and γ_{2} of X are S-homotopic if and only if the corresponding morphisms of globular CW-complexes from \overrightarrow{I} to X are S-homotopic.

Definition 4.5. Let X and Y be two globular CW-complexes. If there exists a morphism f from X to Y and a morphism g from Y to X such that f ∘ g ∼_{S} Id_{Y} and g ∘ f ∼_{S} Id_{X}, then X and Y are said S-homotopic, or S-homotopy equivalent and f and g are two inverse S-homotopy equivalences.

Notice that in the latter case, f ∘ g and Id_{Y} coincide on Y^{0} and g ∘ f and Id_{X} coincide on X^{0}. Therefore if f is a S-homotopy equivalence from X to Y then f induces a bijection between both 0-skeletons.

Of course, Definition 4.5 defines an equivalence relation.

Definition 4.6. Let F be a functor from glCW to some category C. Then F is S-invariant if and only if for any S-homotopy equivalence s, F (s) is an isomorphism in C.

Theorem 4.7. Let S be the collection of S-homotopy equivalences of glCW. There exists a category Ho^{S}(glCW) and a functor

Q^{S} : glCW ⟶ Ho^{S}(glCW)

satisfying the following conditions :

• For every s ∈ S, Q^{S}(s) is invertible in Ho^{S}(glCW).

• For every functor F : glCW ⟶ C such that for every s ∈ S, F (s) is invertible in C, then there exists a unique functor G from Ho^{S}(glCW) to C such that F = G ∘ Q^{S}.

Proof. We mimic the classical proof as presented for instance in [22] : the main idea consists of using the fact that the canonical projection from I^{S}(X) to X is a S-homotopy equivalence, having as inverse both ϵ_{0} and ϵ_{1}.

Let Ho^{S}(glCW) be the category having the same object as glCW and such that

Ho^{S}(glCW)(X, Y) := [X, Y]_{S}.

Let F : glCW ⟶ C be a functor such that for any s ∈ S, Q^{S}(s) is invertible in C. The factorization F = G ∘ Q^{S} is obvious on the objects. To complete the proof, it suffices to verify that for two S-homotopic morphisms f and g, then F (f) = F (g). By definition, there exists \overline{H} from I^{S}(X) to Y such that \overline{H} ∘ ϵ_{0} = f and \overline{H} ∘ ϵ_{1} = g. Let pr_{1} be the canonical projection from I^{S}(X) to X. Then pr_{1}∘ϵ_{0} = pr_{1}∘ϵ_{1} = Id_{X}, ϵ_{0} ∘ pr_{1} ∼_{S} Id_{I^{S}(X)} and ϵ_{1} ∘ pr_{1} ∼_{S} Id_{I^{S}(X)}. Therefore F (pr_{1}) has as inverse both F (ϵ_{0}) and F (ϵ_{1}). Thus F (f) = F (\overline{H}) ∘ F (ϵ_{0}) = F (\overline{H}) ∘ F (ϵ_{1}) = F (g).

Corollary 4.8. Let F be a functor from glCW to some category C. Then F is S-invariant if and only if there exists a functor G from Ho^{S}(glCW) to C such that F = G ∘ Q^{S}.

Example 4.9. The HDA of Figure 11 is obtained by contracting the top-left 2-cell of the HDA of Figure 6. This is a typical example of spatial deformation.

4.2. T-homotopy equivalence

Now we want to treat the case of temporal deformations. Figure 12 is a simple example of temporal deformation of HDA. An obvious bijective morphism f of globular CW-complexes which sends u on the “concatenation” u_{1}u_{2} (such a morphism is of course not unique) and which is the identity elsewhere should be an equivalence. Unfortunately f does not induce a bijection on the 0-skeletons because of the point which appears on the middle of u. So the globular CW-complexes of Figure 12 cannot be S-homotopic. This morphism f induces an homeomorphism between the underlying topological spaces. The inverse f^{−1} is not a morphism of globular CW-complexes because the point between u_{1} and u_{2} is mapped by f^{−1} on a point belonging to the interior of the globular cell u, which is not an element of the 0-skeleton.

It is very intuitive to think that morphisms of glCW inducing homeomorphisms on the underlying topological spaces do not change the computer-scientific properties of the corresponding HDA. In particular, homeomorphisms do not contract

Figure 11: Spatial deformation of the HDA of Figure 6

\xymatrix{α \ar[r]^{u} & β \ar[r]^{v} \ar[r]_{w} & γ}

(a) A 1-dimensional globular CW-complex X

\xymatrix{α_{1} \ar[r]^{u_{1}} & α_{2} \ar[r]^{u_{2}} & β \ar[r]^{v} \ar[r]_{w} & γ}

(b) Subdivision of u in X

Figure 12: Example of temporal deformation

directed segments : this is exactly the kind of properties expected for T-invariance [11]. Hence the following definition :

Definition 4.10. A morphism f of globular CW-complexes from X to Y is a Thomotopy equivalence if and only if f induces an homeomorphism on the underlying topological spaces.

Definition 4.11. Let F be a functor from glCW to some category C. Then F is Tinvariant if and only if for any T-homotopy equivalence t, F (t) is an isomorphism.

Looking back to Figure 12, one sees that there exists a T-homotopy equivalence from the left member to the right one, but not in the reverse direction. So a Thomotopy equivalence is not necessarily an invertible morphism of glCW.

Theorem 4.12. Let T be the collection of T-homotopy equivalences. There exists a category Ho^{T} (glCW) and a functor

Q^{T} : glCW ⟶ Ho^{T} (glCW)

satisfying the following conditions :

• For every t ∈ T, Q^{T} (t) is invertible in Ho^{T} (glCW).

• For every functor F : glCW ⟶ C such that for any t ∈ T, Q^{T} (t) is invertible in C, then there exists a unique functor G from Ho^{T} (glCW) to C such that F = G ∘ Q^{T}.

Proof. There exists a V-small category Ho^{T} (glCW) satisfying the universal property of the theorem and constructed as follows : the objects of Ho^{T} (glCW) are those of glCW. The elements of the V-small set Ho^{T} (glCW)(X, Y) where X and Y are two 1-dimensional globular CW-complexes are of the form

g_{1}f_{1}^{−1}g_{2} … g_{n}f_{n}^{−1}g_{n+1}

with n ⩾ 1 where g_{1}, …, g_{n+1} are morphisms of glCW and f_{1}, …, f_{n} are Thomotopy equivalences and where the notation f^{−1} for f T-homotopy equivalence is a formal inverse of f (see for example [1] Proposition 5.2.2 for the construction).

Let us consider the following commutative diagram

[figure: X; g_{n+1}; cod(g_{n+1}); dom(f_{n}); f_{n}; g_{n}; cod(g_{n}); X; Id; g_{n+1}; f_{n} (\overline{f_{n}^{−1}(g_{n+1}(X))}); ⊂; \overline{f_{n}^{−1}(g_{n+1}(X))}; f_{n}; ⊂; g_{n}; cod(g_{n}); Id]

with the notation cod(h) for the codomain of h, dom(h) for the domain of h, and for A a subset of some globular CW-complex Z,

\overline{A} = ⋃_{x∈A∩Z^{0}}\{x\} ∪ ⋃_{x∈A\Z^{0}} e_{x} ⊂ Z

where e_{x} is the smallest globular cell containing x. We see immediately that |\overline{A}| ⩽ max(2^{ℵ_{0}}, A) where |X| means the cardinal of X and where ℵ_{0} is the smallest infinite cardinal, i.e. that of the set of non-negative integers. Since f_{n} is an homeomorphism and in particular is bijective, then

|f_{n} (\overline{f_{n}^{−1}(g_{n+1}(X))}) | = |\overline{f_{n}^{−1}(g_{n+1}(X))}|
⩽ max(2^{ℵ_{0}}, |f_{n}^{−1}(g_{n+1}(X))|)
= max(2^{ℵ_{0}}, |g_{n+1}(X)|)
⩽ max(2^{ℵ_{0}}, |X|)

This diagram remaining commutative in Ho^{T} (glCW), it shows that we can suppose

|cod(g_{n+1})| ⩽ max(2^{ℵ_{0}}, |X|)

and

|dom(f_{n})| ⩽ max(2^{ℵ_{0}}, |X|)

with an expression like g_{n}f_{n}^{−1}g_{n+1}. By an immediate induction, we see that with a morphism of the form g_{1}f_{1}^{−1}g_{2} … g_{n}f_{n}^{−1}g_{n+1} lying in Ho^{T} (glCW)(X, Y), we can suppose that all intermediate objects are of cardinal lower than max(2^{ℵ_{0}}, |X|) which is an U-small cardinal. Therefore Ho^{T} (glCW)(X, Y) is U-small as well.

Proposition 4.13. Let F be a functor from glCW to some category C. Then F is T-invariant if and only if there exists a functor G from Ho^{T} (glCW) to C such that F = G ∘ Q^{T}.

Let us consider the category Ho^{homeo}(glCW) defined as follows : the objects are the globular CW-complexes ; the set Ho^{homeo}(glCW)(X, Y) is the subset of the set of continuous maps from X to Y consisting of composites of morphisms of globular CW-complexes and continuous maps like f^{−1} where f is a T-homotopy. There exists a canonical functor F : glCW → Ho^{homeo}(glCW) inverting all Thomotopy equivalences. Therefore there exists a unique functor G : Ho^{T} (glCW) → Ho^{homeo}(glCW) such that G ∘ Q = F.

Question 4.14. Why is G an equivalence of categories ?

Example 2.12 is another typical example of T-homotopy equivalence.

4.3. Dihomotopy equivalence

Now we want to take into account both spatial and temporal deformations together.

Definition 4.15. A morphism of globular CW-complexes is called a dihomotopy equivalence if it is the composite of S-homotopy equivalence(s) and T-homotopy equivalence(s).

Theorem 4.16. Let U be the collection of dihomotopy equivalences. There exists a category Ho(glCW) and a functor

Q : glCW ⟶ Ho(glCW)

satisfying the following conditions :

• For every u ∈ U, Q(u) is invertible in Ho(glCW).

• For every functor F : glCW ⟶ C such that for any u ∈ U, Q(u) is invertible in C, then there exists a unique functor G from Ho(glCW) to C such that F = G ∘ Q.

Proof. Let us consider the U-small diagram of categories

\xymatrix{ & glCW \ar[dl]_{Q^{S}} \ar[dr]^{Q^{T}} \\ Ho^{S}(glCW) &  & Ho^{T} (glCW)}

Figure 13: HDA dihomotopy equivalent to the HDA of Figure 5

Then the direct limit of this diagram exists in the large category of V-small categories : see [1] Proposition 5.1.7. By reading the construction in the proof of this latter proposition, one sees that the direct limit is actually a category with U-small objects and U-small homsets.

Proposition 4.17. Let F be a functor from glCW to some category C. Then F is S-invariant and T-invariant if and only if there exists a unique functor G from Ho(glCW) to C such that F = G ∘ Q.

Proof. Obvious.

Definition 4.18. The category Ho(glCW) is called the category of dihomotopy types.

Example 4.19. Figure 13 represents the HDA obtained after applying several spatial and temporal deformations to the HDA of Example 2.9 (cf. Figure 5). Notice that this HDA has the “same computer-scientific properties” as the precubical set from which it was originally built from (see Example 3.10). In particular, it has the same execution paths modulo dihomotopy, and the same set of deadlocks and unreachables.

5. Links between homotopy types and dihomotopy types

Recall that the category of homotopy types Ho(CW) is by definition the category of CW-complexes with continuous maps up to homotopy, i.e. if X and Y are two CW-complexes, then Ho(CW)(X, Y) := [X, Y]. It is well-known that Ho(CW) is the localization of the category CW of CW-complexes with respect to the collection of homotopy equivalences. Theorem 4.7 can be actually considered as a generalization of this fact.

5.1. Path space between two points

Before going any further, we need to define the notion of path space of a bipointed local po-space. Intuitively, applying this operator to a (global) po-space like Glob(X) (where X is a compactly-generated topological space) bipointed by \{\underline{ι}, \underline{σ}\} must give back X up to homotopy.

Definition 5.1. A bipointed local po-space is a triple (X, α, β) where X is a local po-space and α and β are two points of X. A morphism of bipointed local po-spaces from (X, α, β) to (Y, α, β) is a morphism of po-spaces f from X to Y such that f(α) = α and f(β) = β. The corresponding category is denoted by LPoHaus_{∗∗}.

Notice that Glob(−) can be seen as a functor from Haus to LPoHaus_{∗∗} or from Top to PoTop_{∗∗} (the category of bipointed topological spaces with a nonnecessarily closed partial ordering) by bipointing Glob(X) by the elements \underline{ι} and \underline{σ}.

Proposition 5.2. The functor Glob(−) from Top to PoTop_{∗∗} commutes with direct limits.

Proof. Let (X_{i})_{i∈I} be a family of topological spaces. Then

Glob (⨆_{i∈I} X_{i}) = ⨆_{i∈I}(X_{i} × [0, 1]) /\{ \begin{matrix}(z, 0) = (z′, 0) for z, z′ ∈ ⨆_{i∈I} X_{i} \\ (z, 1) = (z′, 1) for z, z′ ∈ ⨆_{i∈I} X_{i} \end{matrix} \}

Note that for all x ∈ Glob (⨆_{i∈I} X_{i}) \{α, β}, there exists a unique i_{x} ∈ I such that x ∈ Glob(X_{i_{x}}). Let (T, α, β) be a bipointed topological space and for all i ∈ I, let ϕ_{i} : Glob(X_{i}) ⟶ (T, α, β) be a morphism in PoTop_{∗∗}. Let ϕ be the set map from Glob (⨆_{i∈I} X_{i}) to T defined by ϕ(α) = α, ϕ(β) = β, and ϕ(x) = ϕ_{i_{x}}(x) (for x ≠ α and x ≠ β). Take (x, t), (x, t′) ∈ Glob (⨆_{i∈I} X_{i}) such that (x, t) ⩽ (x′, t′) We have three possibilities:

• (x, t) = α and ϕ(x, t) = α ⩽ ϕ(x′, t′),

• (x′, t′) = β and ϕ(x, t) ⩽ β = ϕ(x′, t′),

• α < (x, t) ⩽ (x′, t′) < β.

In the latter case, x = x′ and therefore there exists i_{0} ∈ I such that (x, t) and (x′, t′) belong to Glob(X_{i_{0}}). Then ϕ(x, t) = ϕ_{i_{0}}(x, t) ⩽ ϕ_{i_{0}}(x′, t′) = ϕ(x′, t′). The set map ϕ is well-defined and continuous because it is the quotient in Top of the direct sum ⨆_{i∈I} ϕ_{i} by the identifications (z, 0) = (z′, 0) for z, z′ ∈ ⨆_{i∈I} X_{i} and (z, 1) = (z′, 1) for z, z′ ∈ ⨆_{i∈I} X_{i}. Therefore Glob (⨆_{i∈I} X_{i}) is the direct sum of the Glob(X_{i}) for i running over I in PoTop_{∗∗}. So the functor Glob(−) preserves the direct sums.

Let f and g be two continuous maps from X to Y. Let Z = Y /{f(x) ≡ g(x) | x ∈ X} be the coequalizer of (f, g) in Top. Then there exists a surjection

Glob(Y) /{Glob(f)(x, t) ≡ Glob(g)(x, t)} ↠
((Y /\{f(x) = g(x)\}) × [0, 1]) /\{ \begin{matrix}(z, 0) = (z′, 0) \\ (z, 1) = (z′, 1) \end{matrix} \}

which is clearly an homeomorphism. Let (T, α, β) be a bipointed local po-space and let h be a morphism in PoTop_{∗∗} from Glob(Y) to T such that h ∘ Glob(f) = h∘Glob(g). Then h factorizes through Glob(Z) because this latter is the coequalizer of (Glob(f), Glob(g)) in Top. It is easily checked that h is a non-decreasing map and therefore a morphism. So Glob(−) preserves the coequalizers. This entails the result by Proposition 2.9.2 of [1].

Proposition 5.3. The functor Glob(−) from Top to PoTop_{∗∗} has a right adjoint that will be denoted by (−)^{⊥}.

Proof. The category Top has a generator : the one-point space; it is cocomplete and well-copowered. The result follows from the Special Adjoint Functor theorem [25].

If X and Y are two topological spaces, the topological space Cop(X, Y) will be by definition the set Top(X, Y) of continuous maps from X to Y endowed with the compact-open topology : a basis for the open sets consists of the sets N(C, U) where C is any compact subset of X, U any open subset of Y and N(C, U) := {f ∈ Top(X, Y), f(C) ⊂ U}. A topological space is compactly generated when its topology coincides with the weak topology determined by its compact subspaces. If X is a Hausdorff topological space, its Kelleyfication k(X) := \underrightarrow{lim}_{K⊂X} K is a Hausdorff compactly generated topological space where K runs over the set of compact subspaces of X. The Kelleyfication functor k is the right adjoint of the forgetful functor from compactly generated topological spaces to Hausdorff topological spaces. So if X is compactly generated and if Y is Hausdorff, then a set map f : X → Y is continuous if and only if f : X → k(Y) is continuous. The topological space Cop(X, Y) needs not be compactly generated. Let HAUS(X, Y) := k(Cop(X, Y)). Every locally compact Hausdorff topological space is compactly generated. In particular, every CW-complex and every globular CW-complex is compactly generated. The main property of the compact-open topology is the following one : If X, Y and Z are compactly generated, then one has a natural bijection of sets

Top(X × Y, Z) ≅ Top(X, HAUS(Y, Z))  (1)

induced by f ↦ (x ↦ f(x, −)) from the left to the right member and by g ↦ ((x, y) ↦ g(x)(y)) in the opposite direction. As a matter of fact, the isomorphism (1) as topological spaces holds as soon as Y is locally compact Hausdorff.

Proposition 5.4. If (X, α, β) is a bipointed local po-space such that X is compactly generated, then (X, α, β)^{⊥} is homeomorphic to the set of non-decreasing maps γ from [0, 1] to X such that γ(0) = α and γ(1) = β, endowed with the Kelleyfication of the compact-open topology.

Proof. Since [0, 1] is compact,

Top(Y × [0, 1], X) ≅ Top(Y, HAUS([0, 1], X)).

This isomorphism specializes to

\{f : Y × [0, 1] ⟶ X, \begin{matrix}f(y, 0) = α for all y ∈ Y \\ f(y, 1) = β for all y ∈ Y \\ f(y, −) dipath of X \end{matrix} \} ≅ \{g : Y ⟶ HAUS_{α,β}([0, 1], X)\}

where HAUS_{α,β}([0, 1], X) is the set of non-decreasing continuous maps γ from [0, 1] to X such that γ(0) = α and γ(1) = β. The first member is in natural bijection with the morphisms of bipointed po-spaces from Glob(Y) to X, hence the result.

Definition 5.5. For (X, α, β) ∈ PoTop_{∗∗} with X compactly generated, then the topological space

ℙ(X, α, β) := (X, α, β)^{⊥}\{α}

where α is the constant path α, is called the path space of (X, α, β), or the path space of X from α to β. Notice that α ∈ (X, α, β)^{⊥} if and only if α = β.

If ℙGlob(X) is only equipped with the compact-open topology, it will be rather denoted by ℙ^{co}Glob(X). In other terms, ℙGlob(X) = k(ℙ^{co}Glob(X)).

The canonical map i from X to ℙGlob(X) maps any x ∈ X to the dimap t ↦ (x, t) of ℙGlob(X). Now,

Theorem 5.6. For any compactly generated topological space X, the canonical map from X to ℙGlob(X) is an homotopy equivalence.

Proof. Let ϕ ∈ ℙGlob(X). By definition, ϕ is a non-decreasing continuous path from ϕ(0) = \underline{ι} to ϕ(1) = \underline{σ}. Let pr_{2} be the canonical projection of Glob(X) onto [0, 1]. Since ]0, 1[ is open and connected, and pr_{2} and ϕ are continuous, (pr_{2} ∘ ϕ)^{−1}(]0, 1[) is open and connected. Thus we can set (pr_{2} ∘ ϕ)^{−1}(]0, 1[) =]t_{ϕ}^{−}, t_{ϕ}^{+}[. Due to the peculiar ordering we have on Glob(X), ϕ being non-decreasing implies that there exists a unique \underline{x}(ϕ) ∈ X such that for t ∈]t_{ϕ}^{−}, t_{ϕ}^{+}[, ϕ(t) = (\underline{x}(ϕ), pr_{2} ∘ ϕ(t)) (i.e. its first component is constant on ]t_{ϕ}^{−}, t_{ϕ}^{+}[).

Let ϕ_{0} ∈ ℙ^{co}Glob(X) and let U be an open of X containing \underline{x}(ϕ_{0}). Let K_{ϕ_{0}} be a compact subset of ]t_{ϕ_{0}}^{−}, t_{ϕ_{0}}^{+}[. Then ϕ_{0} ∈ N(K_{ϕ_{0}}, U×]0, 1[) and for every ϕ ∈ N(K_{ϕ_{0}}, U×]0, 1[), \underline{x}(ϕ) ∈ U. Therefore the map \underline{x} from ℙ^{co}Glob(X) to X is continuous. Therefore the map still denoted by \underline{x} from ℙGlob(X) to k(X) = X is continuous.

One has \underline{x}∘i = Id_{X} and for all ϕ ∈ ℙGlob(X), i∘\underline{x}(ϕ) is the dimap t ↦ (\underline{x}(ϕ), t). Let

H(ϕ, u)(t) = (\underline{x}(ϕ), ut + (1 − u)pr_{2} ∘ ϕ(t))

Then H yields a set map from ℙGlob(X) × 𝕀 to ℙGlob(X) with H(ϕ, 0) = ϕ and H(ϕ, 1) = i ∘ \underline{x}(ϕ). So it suffices to check the continuity of H to complete the proof.

Consider the set map H′ from ℙ^{co}Glob(X) × 𝕀 × 𝕀 to ℙ^{co}Glob(X) defined by

H′(ϕ, u, t) = (\underline{x}(ϕ), ut + (1 − u)pr_{2} ∘ ϕ(t))

Let C be a compact subset of 𝕀 and U be an open subset of 𝕀 such that pr_{2} ∘ ϕ_{0} ∈ N(C, U) for some ϕ_{0} ∈ ℙ^{co}Glob(X). Then for any ϕ ∈ N(C, X ×U), pr_{2} ∘ϕ(C) ⊂ U. Therefore the set map pr_{2} : ℙ^{co}Glob(X) ⟶ HAUS(𝕀, 𝕀) defined by pr_{2}(ϕ) = pr_{2}∘ϕ is continuous, and the set map H′ is continuous as well. Since the Kelleyfication functor is a right adjoint, it then commutes with products. So k(H′) is a continuous map from ℙGlob(X) × 𝕀 × 𝕀 to ℙGlob(X).

Since H is the image of k(H′) by the canonical isomorphism

Top(ℙGlob(X) × 𝕀 × 𝕀, ℙGlob(X)) ⟶ Top(ℙGlob(X) × 𝕀, HAUS(𝕀, ℙGlob(X)))

H is continuous as well.

5.2. Homotopy and dihomotopy types

We have now the necessary tools in hand to compare homotopy types and dihomotopy types.

Theorem 5.7. Let X and Y be two compactly generated topological spaces. Let f be a morphism of globular complexes from Glob(X) to Glob(Y). Then there exists a unique continuous map f^{S} from X to Y up to homotopy such that f is S-homotopic to Glob(f^{S}).

Proof. Let f_{0} and f_{1} be two continuous maps from X to Y such that Glob(f_{0}) and Glob(f_{1}) are S-homotopic to f. Let H from Glob(X)×𝕀 to Glob(Y) be a S-homotopy from Glob(f_{0}) to Glob(f_{1}) with H_{t} := H(−, t), H_{0} = Glob(f_{0}) and H_{1} = Glob(f_{1}). Consider the set map h from X × 𝕀 to Y defined by h(x, t) = (\underline{x} ∘ ℙ(H_{t}) ∘ i)(x) with the notations of Theorem 5.6. Then

h(x, 0) = (\underline{x} ∘ ℙ(h_{0}) ∘ i)(x)
= (\underline{x} ∘ ℙGlob(f_{0})) (u ↦ (x, u))
= \underline{x} (u ↦ (f_{0}(x), u))
= f_{0}(x)

and in the same manner one gets h(x, 1) = f_{1}(x). So it suffices to prove the continuity of h to prove the uniqueness of f^{S} up to homotopy. We have already proved in Theorem 5.6 the continuity of i and \underline{x}. Therefore it suffices to prove the continuity of the set map (γ, t) ↦ ℙ(H_{t})(γ) = H_{t} ∘ γ from ℙGlob(X) to ℙGlob(Y). This latter map is the composite of

\xymatrix{ℙGlob(X) × 𝕀 \ar[d]_{(γ,t)↦(γ,H,t)} \\ ℙGlob(X) × HAUS(Glob(X) × 𝕀, Glob(Y)) × 𝕀 \ar[d]_{(γ,H,t)↦(γ,H_{t})} \\ ℙGlob(X) × HAUS(Glob(X), Glob(Y)) \ar[d]_{(γ,g)↦g∘γ} \\ ℙGlob(Y)}

The last map (γ, g) ↦ g ∘ γ is the image of the identity map of HAUS(Glob(X), Glob(Y)) by

\xymatrix{Top(HAUS(Glob(X), Glob(Y)), HAUS(Glob(X), Glob(Y))) \ar[d]_{≅} \\ Top(Glob(X) × HAUS(Glob(X), Glob(Y)), Glob(Y)) \ar[d] \\ Top(\overrightarrow{I} × HAUS(\overrightarrow{I}, Glob(X)) × HAUS(Glob(X), Glob(Y)), Glob(Y)) \ar[d]_{≅} \\ Top(HAUS(\overrightarrow{I}, Glob(X)) × HAUS(Glob(X), Glob(Y)), HAUS(\overrightarrow{I}, Glob(Y)))}

and therefore is continuous. At last the set map (H, t) ↦ H_{t} is the image of the identity map of HAUS(Glob(X) × 𝕀, Glob(Y)) by

\xymatrix{Top(HAUS(Glob(X) × 𝕀, Glob(Y)), HAUS(Glob(X) × 𝕀, Glob(Y))) \ar[d] \\ Top(Glob(X) × 𝕀 × HAUS(Glob(X) × 𝕀, Glob(Y)), Glob(Y)) \ar[d]_{≅} \\ Top(𝕀 × HAUS(Glob(X) × 𝕀, Glob(Y)), HAUS(Glob(X), Glob(Y)))}

and therefore is also continuous. So h is an homotopy between f_{0} and f_{1}.

Now set f^{S} := \underline{x} ∘ ℙ(f) ∘ i from X to Y. With the proof of Theorem 5.6, we see immediately that f^{S} is continuous. It remains to prove that Glob(f^{S}) is S-homotopic to f. We have already seen in the proof of Theorem 5.6 that for ϕ ∈ ℙGlob(X),

ϕ(t) = (\underline{x}(ϕ), pr_{2} ∘ ϕ(t))  (2)

for t ∈]t_{ϕ}^{−}, t_{ϕ}^{+}[. For t ∈ [0, t_{ϕ}^{−}] (resp. t ∈ [t_{ϕ}^{+}, 1]), one has by definition pr_{2} ∘ ϕ(t) = 0

(resp. pr_{2} ∘ϕ(t) = 1) and therefore Equality 2 is still true for any t ∈ \overrightarrow{I}. So consider the path ϕ_{x} : t ↦ (x, t) of ℙGlob(X). Then f ∘ ϕ_{x} is an element of ℙGlob(Y) and we have f ∘ ϕ_{x} = (\underline{x}(f ∘ ϕ_{x}), pr_{2} ∘ f ∘ ϕ_{x}(t)). But \underline{x}(f ∘ ϕ_{x}) = f^{S}(x). Therefore f = (f^{S}, pr_{2} ∘ f). So f is S-homotopic to Glob(f^{S}) with the S-homotopy H from Glob(X)×𝕀 to Glob(Y) defined by H((x, t), u) = (f^{S}(x), ut+(1−u)pr_{2}∘f(x, t)).

Corollary 5.8. Let X and Y be two compactly generated topological spaces. The functor Glob(−) induces a bijection of sets [X, Y] ≅ [Glob(X), Glob(Y)]_{S}.

We arrive at

Theorem 5.9. The mapping X ↦ Glob(X) induces an embedding

Ho(CW) ↪ Ho(glCW).

Proof. This is a consequence of Proposition 2.7, Proposition 2.11 and Theorem 5.7.

See the consequences of this important theorem in [13] where a research program to investigate dihomotopy types is exposed.

5.3. Towards a Whitehead theorem Now we want to weaken the notion of S-homotopy equivalence.

Definition 5.10. Let f be a morphism of globular CW-complexes from X to Y. Then f is a weak S-homotopy equivalence if the following conditions are fulfilled :

1. the map f induces a set bijection between the 0-skeleton of X and the 0-skeleton of Y.

2. for α, β ∈ X^{0}, f induces a weak homotopy equivalence from ℙ(X, α, β) to ℙ(Y, f(α), f(β)).

Proposition 5.11. Let f be a morphism of globular CW-complexes from X to Y. If f is a S-homotopy from X to Y, then f is a weak S-homotopy equivalence.

Proof. Let g be a S-homotopy from Y to X such that f∘g ∼_{di} Id_{Y} and g∘f ∼_{di} Id_{X}. Then f ∘ g and Id_{Y} (resp. g ∘ f and Id_{X}) coincide on Y^{0} (resp. X^{0}). Therefore f induces a bijection of sets from the 0-skeleton X^{0} to the 0-skeleton Y^{0} with inverse the restriction of g to Y^{0}. Let α and β be two elements of X^{0}. Then f (resp. g) induces a continuous map f_{∗} from ℙ(X, α, β) (resp. g_{∗} from ℙ(Y, f(α), f(β))) to ℙ(Y, f(α), f(β)) (resp. ℙ(X, α, β)). Let H be a continuous map from Y × 𝕀 to Y which is a S-homotopy from f ∘ g to Id_{Y}. Let H_{u} = H(−, u). By hypothesis, this is a morphism of globular CW-complexes from Y to itself which induces the identity map on Y^{0}. Let h(γ, u) := H_{u} ∘ γ. Then h(γ, u)(0) = H_{u}(γ(0)) = H_{u}(f(α)) = f(α) and h(γ, u)(1) = H_{u}(γ(1)) = H_{u}(f(β)) = f(β). Moreover h(γ, u) is non-decreasing and continuous because it is the composite of two functions which are non-decreasing and continuous as well. Therefore h is a set map from ℙ(Y, f(α), f(β)) × 𝕀 to ℙ(Y, f(α), f(β)). We have already proved the continuity of similar maps (as in Theorem 5.7). Therefore f_{∗} ∘ g_{∗} ∼ Id_{ℙ(Y,f(α),f(β))}. Similarly, we can prove that g_{∗} ∘ f_{∗} ∼ Id_{ℙ(X,α,β)}. Therefore f is a weak S-homotopy equivalence.

The converse of Proposition 5.11 gives rise to the following

Conjecture 5.12. ^{8}

Let f be a morphism of globular CW-complexes from X to Y. Then the following assumptions are equivalent :

1. f is a weak S-homotopy equivalence.

2. f is a S-homotopy equivalence.

In the case of globes, one has :

Proposition 5.13. Let f be a morphism of globular CW-complexes from Glob(X) to Glob(Y) where X and Y are two connected CW-complexes. If f is a weak Shomotopy equivalence, then there exists a morphism of globular CW-complexes g from Glob(Y) to Glob(X) such that g ∘ f is S-homotopic to the identity of Glob(X) and f ∘ g S-homotopic to the identity of Glob(Y).

Proof. The composite \underline{x} ∘ ℙ(f) ∘ i

\xymatrix{X \ar[r] & ℙGlob(X) \ar[r]^{ℙ(f)} & ℙGlob(Y) \ar[r] & Y}

is a homotopy equivalence of CW-complexes because ℙ(f) is an homotopy equivalence by hypothesis and because of Theorem 5.6. Therefore \underline{x} ∘ ℙ(f) ∘ i has an inverse g up to homotopy from Y to X. By Corollary 5.8, Glob(\underline{x}∘ℙ(f)∘i)∘Glob(g) and Glob(g) ∘ Glob(\underline{x} ∘ ℙ(f) ∘ i) are S-homotopic to the identity (resp. of Glob(Y) and Glob(X)). Again by Corollary 5.8, Glob(\underline{x} ∘ ℙ(f) ∘ i) and f are S-homotopic. Therefore

Glob(g) ∘ f ∼_{S} Glob(g) ∘ Glob(\underline{x} ∘ ℙ(f) ∘ i) ∼_{S} Id

and

f ∘ Glob(g) ∼_{S} Glob(\underline{x} ∘ ℙ(f) ∘ i) ∘ Glob(g) ∼_{S} Id.

6. Why non-contracting maps ?

We would like to explain here why one imposes the morphisms of globular CWcomplexes to be non-contracting in Definition 2.10, why in Definition 5.5 the constant dipath is removed from ℙ(X, α, β) if α = β. As a matter of fact, there are a lot of technical reasons to do that which will be clearer in the future developments. This section focuses on a very striking one.

The fundamental algebraic structure which has emerged from the ω-categorical approach [12, 10, 14] is the diagram of Figure 14 where C is an ω-category. The analogue in the globular CW-complex framework is the diagram of Figure 15 where ℙX is the space of dipaths between two elements of the 0-skeleton of X, and ℙ^{−}X (resp. ℙ^{+}X) is the space of germs of dipaths starting from (resp. ending at) a point of the 0-skeleton of X.

8This conjecture has been actually solved later on [9].

\xymatrix{ & N^{gl}(C) \ar[dl]_{h^{−}} \ar[dr]^{h^{+}} \\ N^{gl^{−}}(C) &  & N^{gl^{+}}(C)}

Figure 14: The fundamental diagram

\xymatrix{ & ℙX \ar[dl]_{h^{−}} \ar[dr]^{h^{+}} \\ ℙ^{−}X &  & ℙ^{+}X}

Figure 15: The fundamental diagram for a globular CW-complex X

Let us suppose just for this section that the path space of a globular CW-complex X is defined as follows :

ℙX = ⨆_{(α,β)∈X^{0}×X^{0}}(X, α, β)^{⊥}

and that the semi-path spaces of a globular CW-complex X are defined as follows :

ℙ^{−}X = ⨆_{α∈X^{0}}(X, α)^{⊥^{−}}

ℙ^{+}X = ⨆_{α∈X^{0}}(X, α)^{⊥^{+}}

where (X, α)^{⊥^{−}} (resp. (X, α)^{⊥^{+}}) is the set of dipaths of X starting from α (ending at α), and endowed with the compact-open topology. Then the maps h^{−} and h^{+} of Figure 15 are obviously defined. However

Proposition 6.1. (Remark due to Stefan Sokolowski) The topological spaces ℙ^{−}X and ℙ^{+}X are homotopy equivalent to the discrete set X^{0} (the 0-skeleton of X) !

Proof. Let us make the proof for ℙ^{−}X. The canonical map u : X^{0} ↪ ℙ^{−}X sends an α ∈ X^{0} on the corresponding constant dipaths of ℙ^{−}X. The map u is necessarily continuous since X^{0} is discrete. In the other direction, let us consider the set map v : ℙ^{−}X → X^{0} defined by v(γ) = γ(0) : such an evaluation map is necessarily continuous as soon as ℙ^{−}X is endowed with the compact-open topology. Then v ∘ u = Id_{X^{0}} and u ∘ v is homotopic to Id_{ℙ^{−}X} by the homotopy

H : ℙ^{−}X × 𝕀 → ℙ^{−}X

defined by H(γ, u)(t) := γ(tu). The map H is the image of the identity of HAUS(\overrightarrow{I}, X) by

\xymatrix{Top(HAUS(\overrightarrow{I}, X), HAUS(\overrightarrow{I}, X)) \ar[d]_{≅} \\ Top(\overrightarrow{I} × HAUS(\overrightarrow{I}, X), X) \ar[d]_{ϕ} \\ Top(\overrightarrow{I} × HAUS(\overrightarrow{I}, X) × 𝕀, X) \ar[d]_{≅} \\ Top(HAUS(\overrightarrow{I}, X) × 𝕀, HAUS(\overrightarrow{I}, X))}

where ϕ is induced by the mapping (t, u) ↦ tu from \overrightarrow{I} × 𝕀 to \overrightarrow{I} and therefore H is continuous.

Therefore ℙ^{−}X and ℙ^{+}X defined as above contain no relevant information ! This fact is exactly the analogue of [12] Proposition 4.2 which states that the cubical nerve of an ω-category has a trivial simplicial homology with respect to ∂^{−} and ∂^{+} and which led to introducing ωCat(I^{∗}, C)^{−} and ωCat(I^{∗}, C)^{+}.

So the correct definition of ℙ^{−}X and ℙ^{+}X is :

ℙ^{−}X = ⨆_{α∈X^{0}}(X, α)^{⊥^{−}}\{α}

ℙ^{+}X = ⨆_{α∈X^{0}}(X, α)^{⊥^{+}}\{α}

Now the maps ℙX → ℙ^{−}X and ℙX → ℙ^{+}X do not exist anymore ! To recover these important maps, it is necessary to set :

ℙX = ⨆_{(α,β)∈X^{0}×X^{0}} ℙ(X, α, β)

Then the only way to make the mapping ℙ (and also ℙ^{−} and ℙ^{+}) a functor from the category glCW of globular CW-complexes to that of compactly-generated topological spaces is to impose to morphisms in glCW to be non-contracting as explained in Definition 2.10.

7. Concluding remarks and some open questions

We have constructed a category of dihomotopy types whose isomorphism classes of objects represent exactly higher dimensional automata modulo deformations leaving invariant computer-scientific properties as presence or not of deadlock or everything related. This construction provides a rigorous definition of S-deformations (Definition 4.6) and T-deformations (Definition 4.11) of HDA. Using the definitions of [13], it is trivial to prove the S-invariance of all functors like H_{∗}^{gl}, H_{∗}^{gl^{±}}, etc...

Question 7.1. Proving the T-invariance of both semi-globular homology theories H_{∗}^{gl^{±}}.

Question 7.2. Same question for the biglobular homology defined in [10].

By analogy with the situation in usual algebraic topology :

Question 7.3. Defining a notion of weak dihomotopy equivalence on the category of local po-spaces ; Proving that the localization of the category of local po-spaces with respect to this collection of morphisms exists and that it is isomorphic to the category of dihomotopy types.

The realization functor from a (quite large) subcategory of precubical sets (the “non-self-linked” ones) to the category of local po-spaces constructed in [6] and the realization functor constructed in Section 3.3 must be compared, which leads to the following

Question 7.4. Proving that for a non-self linked precubical set, both realization functors give the same local po-spaces up to dihomotopy ; so a notion of dihomotopic local po-spaces is needed.

In sequential computation theory, there are nice algebraic topological results which should relate to the present theory.

A monoïd (M, 1, .) (1 is the neutral element for the monoidal operation .) is finitely presented (respectively finitely presented by a rewriting system) if there exists a finite set of symbols S and a finite set of relations R on S^{∗}, the free monoid on S (respectively of directed rewrite rules of the form u rewrites into v, u, v in S^{∗}), such that M ≅ S^{∗}/R (respectively such that M is isomorphic to S^{∗} quotiented by the congruence generated by R). We say that a monoïd (M, 1, .) has a decidable word problem if there exists an algorithm which can decide in a finite time whether two words of M are equal.

We say that a rewriting system is canonical if given any word w in S^{∗}, any sequence of reductions (i.e. sequence of applications of any of the rewrite rules) is finite, and if all sequences of reductions (since many different reductions can apply at the same time on the same word) end at the same word. This last word is called the canonical form of w and is used to decide equality of two representatives of words in M.

Squier’s theorem shows that all finitely presented monoïds with a decidable word problem cannot be presented by a finite canonical rewriting system. In fact, it tells us a lot more: if M can be presented by a finite canonical rewriting system, then the third homology group of M is of finite type. In fact, we can even prove [23, 29] that all homology groups are of finite type. One of the resolutions [19] constructs a cubical set on which the monoïd acts freely on the left. This means that all orbits of points under the action of M are trajectories on a cubical set; then, the homology of the monoïd is the homology of the quotient space of the geometric realization of the cubical set constructed under the relation, being on the same orbit.

It is well known that in the case of monoïds, having finite type homology groups does not imply the existence of a finite canonical rewrite system presenting the monoïd, whereas in the case of groups, more things are known. This “defect” is partly due to the fact that we forget in the classical homological construction the “direction of time” represented by the (non-commutative and non-invertible in general) monoïdal operation. It is also probably due to the fact that the real criterion would have to be homotopical and not just homological. These ideas are already reflected in [29] and in the more recent one [24]. In fact, in the case of concurrency theory, we only deal with “partially commutative” monoïds i.e. free monoïds modulo the commutativity of certains pair of actions, or of certains n-uples of actions. This is only a particular case, which is more general in the case of rewriting systems. As a matter of fact, in [24], the relations of the monoïd are presented by 2-cells in a 2-category (i.e. homotopies between [di-]paths!).

In modern terms, the homology of a monoïd is the homology of its classifying space. The classifying space is just the geometric realization of the nerve of the monoïd (considered as a one-object category). Our point of view is that the globular homology of the monoïd (i.e. the homology of the globular nerve of the monoïd) is an “invariant” of the monoïd, i.e. will not change when we change the presentation (change the set of symbols and relations). The problem is that this globular homology is far too big (in general of infinite rank) for our purposes. For it to be reasonable, it would have to be somehow invariant under subdivisions. This is currently under investigation.

Acknowledgments

The authors thank Gunnar Carlsson and Rick Jardine for the invitation to the conference “Algebraic Topological Methods in Computer Science” held in Stanford in August 2001. We also wish to thank the anonymous referees and Martin Raussen for helpful comments.

References

[1] Borceux, F., “Handbook of categorical algebra. 1,” Cambridge University Press, Cambridge, 1994, xvi+345 pp., basic category theory.

[2] Brown, R. and P. J. Higgins, On the algebra of cubes, J. Pure Appl. Algebra 21 (1981), pp. 233–260.

[3] Coffman, E. G., M. J. Elphick and A. Shoshani, System deadlocks, Computing Surveys 3 (1971), pp. 67–78.

[4] Dijkstra, E., “Cooperating Sequential Processes,” Academic Press, 1968.

[5] Fajstrup, L., E. Goubault and M. Raussen, Detecting deadlocks in concurrent systems, in: Proceedings of the 9th International Conference on Concurrency Theory, also available at http://www.di.ens.fr/˜ goubault (1998).

[6] Fajstrup, L., E. Goubault and M. Raussen, Algebraic topology and concurrency, to appear in Theoretical Computer Science, also technical report, Aalborg University, see http://www.di.ens.fr/˜ goubault/ (1999).

[7] Fajstrup, L. and M. Raussen, Detecting deadlocks in concurrent systems, Technical report, BRICS Research Report, Aalborg University (1996).

[8] Gabriel, P. and M. Zisman, “Calculus of fractions and homotopy theory,” Springer-Verlag New York, Inc., New York, 1967, x+168 pp.

[9] Gaucher, P., Whitehead’s Theorem in Homotopy Theory of Concurrency, arxiv:math.AT/0201252.

[10] Gaucher, P., About the globular homology of higher dimensional automata (2000), arxiv:math.CT/0002216, to appear in Cahiers Top. Géom. Diff. Catég.

[11] Gaucher, P., From concurrency to algebraic topology, Electronic Notes in Theoretical Computer Science 39 (2000), p. 19pp.

[12] Gaucher, P., Homotopy invariants of higher dimensional categories and concurrency in computer science, Math. Structures Comput. Sci. 10 (2000), pp. 481–524.

[13] Gaucher, P., Investigating The Algebraic Structure of Dihomotopy Types (2001), arxiv:math.AT/0105049, to appear in Electronic Notes in Theoretical Computer Science, volume 52/2.

[14] Gaucher, P., The branching nerve of HDA and the Kan condition (2001), arxiv:math.AT/0103011.

[15] Goubault, E., “The Geometry of Concurrency,” Ph.D. thesis, École Normale Supérieure (1995).

[16] Goubault, E., Geometry and concurrency: A users’ guide, Mathematical Structures in Computer Science (2000).

[17] Grandis, M., Directed homotopy theory, I. the fundamental category, Cahiers Top. Géom. Diff. Catég., to appear (2001).

[18] Grandis, M., Directed homotopy theory, II. homotopy constructs, Technical report, Dip. Mat. Univ. Genova, Preprint 446 (2001).

[19] Groves, J. R. J., Rewriting systems and homology of groups, in: L. G. Kovacs, editor, Groups – Canberra 1989, 1456 (1991), pp. 114–141.

[20] Hatcher, A., Algebraic topology, http://www.math.cornell.edu/˜ hatcher/.

[21] Johnstone, P. T., “Stone Spaces,” Cambridge University Press, 1982.

[22] Kamps, K. H. and T. Porter, “Abstract homotopy and simple homotopy theory,” World Scientific Publishing Co. Inc., River Edge, NJ, 1997, x+462 pp.

[23] Kobayashi, Y., Complete rewriting systems and homology of monoid algebras, Journal of Pure and Applied Algebra 65 (1990), pp. 263–275.

[24] Lafont, Y., A new finiteness condition for monoids presented by complete rewriting systems, Journal of Pure and Applied Algebra 98 (1995).

[25] Mac Lane, S., “Categories for the working mathematician,” Springer-Verlag, New York, 1998, second edition, xii+314 pp.

[26] Nachbin, L., “Topology and Order,” Van Nostrand, Princeton, 1965.

[27] Pratt, V., Modeling concurrency with geometry, in: Proc. of the 18th ACM Symposium on Principles of Programming Languages (1991).

[28] Rotman, J. J., “An introduction to algebraic topology,” Springer-Verlag, New York, 1988, xiv+433 pp.

[29] Squier, C. C., F. Otto and Y. Kobayashi, A finiteness condition for rewriting systems, Theoretical Computer Science 131 (1994), pp. 271–294.

This article may be accessed via WWW at http://www.rmi.acnet.ge/hha/ or by anonymous ftp at

ftp://ftp.rmi.acnet.ge/pub/hha/volumes/2003/n2a3/v5n2a3.(dvi,ps,pdf)

Philippe Gaucher gaucher@math.u-strasbg.fr
http://www-irma.u-strasbg.fr/~gaucher

Institut de Recherche Mathématique Avancée, ULP et CNRS, 7 rue René Descartes, 67084 Strasbourg Cedex

Eric Goubault Eric.Goubault@cea.fr
http://www.di.ens.fr/~goubault

LIST (CEA - Recherche Technologique) DTSI-SLA, CEA F91191 Gif-sur-Yvette Cedex