Homology, Homotopy and Applications, vol.7(1), 2005, pp.51–76

HOMOLOGICAL PROPERTIES OF NON-DETERMINISTIC BRANCHINGS AND MERGINGS IN HIGHER DIMENSIONAL

AUTOMATA

PHILIPPE GAUCHER

(communicated by Mark Hovey)

Abstract The branching (resp. merging) space functor of a flow is a left Quillen functor. The associated derived functor allows to define the branching (resp. merging) homology of a flow. It is then proved that this homology theory is a dihomotopy invariant and that higher dimensional branchings (resp. mergings) satisfy a long exact sequence.

1. Introduction

The category of flows [4] is an algebraic topological model of higher dimensional automata [14] [6]. Two kinds of mathematical problems are particularly of importance for such objects: 1) reducing the size of the category of flows by the introduction of a class of dihomotopy equivalences identifying flows having the same computer-scientific properties ; 2) investigating the mathematical properties of these dihomotopy equivalences for instance by constructing related model category structures and algebraic invariants. For other examples of similar investigations with different algebraic topological models of concurrency, cf. for example [9] [2] [8].

This paper is concerned with the second kind of mathematical problems. Indeed, the purpose of this work is the construction of two dihomotopy invariants, the branching homology H_{∗}^{−}(X) and the merging homology H_{∗}^{+}(X) of a flow X, detecting the non-deterministic branching areas (resp. merging areas) of non-constant execution paths in the higher dimensional automaton modelled by the flow X. Dihomotopy invariance means in the framework of flows invariant with respect to weak S-homotopy (Corollary 6.5) and with respect to T-homotopy (Proposition 7.4).

The core of the paper is focused on the case of branchings. The case of mergings is similar and is postponed to Appendix A.

The branching space of a flow is introduced in Section 3 after some reminders about flows themselves in Section 2. Loosely speaking, the branching space of a flow is the space of germs of non-constant execution paths beginning in the same way. This functor is the main ingredient in the construction of the branching homology.

Received November 3, 2004; published on May 16, 2005. 2000 Mathematics Subject Classification: 55P99, 55N35, 68Q85. Key words and phrases: concurrency, homotopy, branching, merging, homology, left Quillen functor, long exact sequence, Mayer-Vietoris, cone, higher dimensional automata, directed homotopy. \begin{matrix}c \\ ◯ \end{matrix} 2005, Philippe Gaucher. Permission to copy for private use granted.

However it is badly behaved with respect to weak S-homotopy equivalences, as proved in Section 4. Therefore it cannot be directly used for the construction of a dihomotopy invariant. This problem is overcome in Section 5 by introducing the homotopy branching space of a flow: compare Theorem 4.1 and Corollary 5.7. The link between the homotopy branching space and the branching space is that they coincide up to homotopy for cofibrant flows, and the latter are the only interesting and real examples (Proposition 9.1).

Using this new functor, the branching homology is finally constructed in Section 6 and it is proved in the same section and in Section 7 that it is a dihomotopy invariant (Corollary 6.5 and Proposition 7.4).

Section 8 uses the previous construction to establish the following long exact sequence for higher dimensional branchings:

Theorem. For any morphism of flows f : X ⟶ Y, one has the long exact sequence

⋯ → H_{n}^{−}(X) → H_{n}^{−}(Y) → H_{n}^{−}(Cf) → …
⋯ → H_{3}^{−}(X) → H_{3}^{−}(Y) → H_{3}^{−}(Cf) →
H_{2}^{−}(X) → H_{2}^{−}(Y) → H_{2}^{−}(Cf) →
H_{0}(hoℙ^{−} X) → H_{0}(hoℙ^{−} Y) → H_{0}(hoℙ^{−} Cf) → 0.

where Cf is the cone of f and where H_{0}(hoℙ^{−} Z) is the free abelian group generated by the path-connected components of the homotopy branching space of the flow Z.

By now, this homological result does not have any known computer scientific interpretation. But it sheds some light on the potential of an algebraic topological approach of concurrency.

At last, Section 9 then gives several examples of calculation which illustrate the mathematical notions presented here.

Appendix B is a technical section which proves that two S-homotopy equivalent flows (which are not necessary cofibrant) have homotopy equivalent branching spaces. The result is not useful at all for the core of the paper but is interesting enough to be presented in an appendix of a paper devoted to branching homology.

Some familiarity with model categories is required for a good understanding of this work. However some reminders are included in this paper. Possible references for model categories are [11], [10] and [3]. The original reference is [15].

2. The category of flows

In this paper, Top is the category of compactly generated topological spaces, i.e. of weak Hausdorff k-spaces (cf. [1], [13] and the appendix of [12]).

Definition 2.1. Let i : A ⟶ B and p : X ⟶ Y be maps in a category C. Then i has the left lifting property (LLP) with respect to p (or p has the right lifting property (RLP) with respect to i) if for any commutative square

\xymatrix{A \ar[d]_{i} \ar[r]^{α} & X \ar[d]_{p} \\ B \ar@{-->}[ur]^{g} \ar[r]^{β} & Y}

there exists g making both triangles commutative.

The category Top is equipped with the unique model structure having the weak homotopy equivalences as weak equivalences and having the Serre fibrations ^{1} as fibrations.

Definition 2.2. [4] A flow X consists of a compactly generated topological space ℙX, a discrete space X^{0}, two continuous maps s and t called respectively the source map and the target map from ℙX to X^{0} and a continuous and associative map ∗ : {(x, y) ∈ ℙX × ℙX; t(x) = s(y)} ⟶ ℙX such that s(x ∗ y) = s(x) and t(x ∗ y) = t(y). A morphism of flows f : X ⟶ Y consists of a set map f^{0} : X^{0} ⟶ Y^{0} together with a continuous map ℙf : ℙX ⟶ ℙY such that f(s(x)) = s(f(x)), f(t(x)) = t(f(x)) and f(x ∗ y) = f(x) ∗ f(y). The corresponding category is denoted by Flow.

The topological space X^{0} is called the 0-skeleton of X. The elements of the 0skeleton X^{0} are called states or constant execution paths. The elements of ℙX are called non-constant execution paths. An initial state (resp. a final state) is a state which is not the target (resp. the source) of any non-constant execution path. The initial flow is denoted by ∅. The terminal flow is denoted by 1. The initial flow ∅ is of course the unique flow such that ∅^{0} = ℙ∅ = ∅ (the empty set). The terminal flow is defined by 1^{0} = {0}, ℙ1 = {u} and the composition law u ∗ u = u.

Notation 2.3. [4] For α, β ∈ X^{0}, let ℙ_{α,β}X be the subspace of ℙX equipped with the Kelleyfication of the relative topology consisting of the non-constant execution paths γ of X with beginning s(γ) = α and with ending t(γ) = β.

Several examples of flows are presented in Section 9. But two examples are important for the sequel:

Definition 2.4. [4] Let Z be a topological space. Then the globe of Z is the flow Glob(Z) defined as follows: Glob(Z)^{0} = {0, 1}, ℙGlob(Z) = Z, s = 0, t = 1 and the composition law is trivial. The mapping Glob : Top ⟶ Flow gives rise to a functor in an obvious way.

Notation 2.5. [4] If Z and T are two topological spaces, then the flow

Glob(Z) ∗ Glob(T)

1that is a continuous map having the RLP with respect to the inclusion D^{n} × 0 ⊂ D^{n} × [0, 1] for any n ⩾ 0 where D^{n} is the n-dimensional disk

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

is the flow obtained by identifying the final state of Glob(Z) with the initial state of Glob(T). In other terms, one has the pushout of flows:

[figure: {0}; 0↦1; 0↦0; Glob(Z); Glob(T); Glob(Z) ∗ Glob(T)]

3. The branching space of a flow

Loosely speaking, the branching space of a flow is the space of germs of nonconstant execution paths beginning in the same way.

Proposition 3.1. Let X be a flow. There exists a topological space ℙ^{−}X unique up to homeomorphism and a continuous map h^{−} : ℙX ⟶ ℙ^{−}X satisfying the following universal property:

1. For any x and y in ℙX such that t(x) = s(y), the equality h^{−}(x) = h^{−}(x ∗ y) holds.

2. Let ϕ : ℙX ⟶ Y be a continuous map such that for any x and y of ℙX such that t(x) = s(y), the equality ϕ(x) = ϕ(x ∗ y) holds. Then there exists a unique continuous map \overline{ϕ} : ℙ^{−}X ⟶ Y such that ϕ = \overline{ϕ} ∘ h^{−}.

Moreover, one has the homeomorphism

ℙ^{−}X ≅ ⨆_{α∈X^{0}} ℙ_{α}^{−}X

where ℙ_{α}^{−}X := h^{−} (⨆_{β∈X^{0}} ℙ_{α,β}^{−}X). The mapping X ↦ ℙ^{−}X yields a functor ℙ^{−} from Flow to Top.

Proof. Consider the intersection of all equivalence relations whose graph is closed in ℙX × ℙX and containing the pairs (x, x ∗ y) for any x ∈ ℙX and any y ∈ ℙX such that t(x) = s(y): one obtains an equivalence relation R^{−}. The quotient ℙX/R^{−} equipped with the final topology is still a k-space since the colimit is the same in the category of k-spaces and in the category of general topological spaces, and is weak Hausdorff as well since the diagonal of ℙX/R^{−} is closed in ℙX/R^{−} ×ℙX/R^{−}. Let ϕ : ℙX ⟶ Y be a continuous map such that for any x and y of ℙX with t(x) = s(y), the equality ϕ(x) = ϕ(x ∗ y) holds. Then the equivalence relation on ℙX defined by “x equivalent to y if and only if ϕ(x) = ϕ(y)” has a closed graph which contains the graph of R^{−}. Hence the remaining part of the statement.

Definition 3.2. Let X be a flow. The topological space ℙ^{−}X is called the branching space of the flow X. The functor ℙ^{−} is called the branching space functor.

4. Bad behaviour of the branching space functor

The purpose of this section is the proof of the following fact:

Theorem 4.1. There exists a weak S-homotopy equivalence of flows f : X ⟶ Y such that the topological spaces ℙ^{−}X and ℙ^{−}Y are not weakly homotopy equivalent.

In other terms, the branching space functor alone is not appropriate for the construction of dihomotopy invariants.

Lemma 4.2. Let Z be a flow such that Z^{0} = {α, β, γ} and such that ℙZ = ℙ_{α,β}Z⊔ℙ_{β,γ}Z⊔ℙ_{α,γ}Z. Such a flow Z is entirely characterized by the three topological spaces ℙ_{α,β}Z, ℙ_{β,γ}Z and ℙ_{α,γ}Z and the continuous map ℙ_{α,β}Z × ℙ_{β,γ}Z ⟶ ℙ_{α,γ}Z. Moreover, one has the pushout of topological spaces

[figure: ℙ_{α,β}Z × ℙ_{β,γ}Z; ∗; ℙ_{α,γ}Z; ℙ_{α,β}Z; ℙ_{α}^{−}Z]

and the isomorphisms of topological spaces ℙ_{β}^{−}Z ≅ ℙ_{β,γ}Z and ℙ^{−}Z ≅ ℙ_{α}^{−}Z ⊔ ℙ_{β}^{−}Z.

Proof. It suffices to check that the universal property of Proposition 3.1 is satisfied by ℙ^{−}Z.

For n ⩾ 1, let D^{n} be the closed n-dimensional disk and let S^{n−1} be its boundary. Let D^{0} = {0}. Let S^{−1} = ∅ be the empty space.

Let X and Y be the flows defined as follows:

1. X^{0} = Y^{0} = {α, β, γ}

2. ℙ_{α,β}X = ℙ_{β,γ}X = {0}

3. ℙ_{α,β}Y = ℙ_{β,γ}Y = ℝ

4. ℙ_{α,γ}X = ℙ_{α,γ}Y = S^{2}

5. the composition law ℙ_{α,β}X × ℙ_{β,γ}X ⟶ ℙ_{α,γ}X is given by the constant map (0, 0) ↦ (0, 0, 1) ∈ S^{2}

Figure 2: ||ϕ(x, y)|| = ^{\frac{\sqrt{x^{2}+y^{2}}}{1+\sqrt{x^{2}+y^{2}}}}

6. the composition law ℙ_{α,β}Y × ℙ_{β,γ}Y ⟶ ℙ_{α,γ}Y is given by the composite

\xymatrix{ℝ × ℝ \ar[r]^{ϕ} & D^{2}\S^{1} \ar@{^{(}->}[r] & D^{2} ⊔_{S^{1}} \{(1, 0, 0)\} ≅ S^{2}}

where ϕ is the homeomorphism (cf. Figure 2) defined by

ϕ(x, y) = (\frac{x}{1 + \sqrt{x^{2} + y^{2}}} , \frac{y}{1 + \sqrt{x^{2} + y^{2}}} )

Then one has the pushouts of compactly generated topological spaces

[figure: {0} × {0}; S^{2}; {0}; ℙ_{α}^{−}X]

and

[figure: ℝ × ℝ; S^{2}; ℝ; ℙ_{α}^{−}Y]

Lemma 4.3. One has the pushout of compactly generated topological spaces

[figure: ℝ × ℝ; D^{2} ⊔_{S^{1}} {(1, 0, 0)} ≅ S^{2}; ℝ; {(1, 0, 0)}]

Proof. Let kTop be the category of k-spaces. It is well known that the inclusion functor i : Top ⟶ kTop has a left adjoint w : kTop ⟶ Top such that w ∘ i = Id_{Top}. So, first of all, one has to calculate the pushout in the category of k-spaces:

[figure: ℝ × ℝ; D^{2} ⊔_{S^{1}} {(1, 0, 0)} ≅ S^{2}; ℝ; X]

and then, one has to prove that {(1, 0, 0)} ≅ w(X).

Colimits in kTop are calculated by taking the colimit of the underlying diagram of sets and by endowing the result with the final topology. The colimit of the underlying diagram of sets is exactly the disjoint sum ℝ ⊔ {(1, 0, 0)}. A subset Ω of ℝ ⊔ {(1, 0, 0)} is open for the final topology if and only its inverse images in ℝ and S^{2} are both open. The inverse image of Ω in ℝ is exactly Ω\{(1, 0, 0)}. The inverse image of Ω in ℝ × ℝ is exactly Ω\{(1, 0, 0)} × ℝ. Therefore the inverse image of Ω in S^{2} is equal to ϕ(Ω\{(1, 0, 0)} × ℝ) if (1, 0, 0) ∉ Ω, and is equal to ϕ(Ω\{(1, 0, 0)} × ℝ) ∪ {(1, 0, 0)} if (1, 0, 0) ∈ Ω. There are thus now two mutually exclusive cases:

1. (1, 0, 0) ∉ Ω; in this case, Ω is open if and only if it is open in ℝ

2. (1, 0, 0) ∈ Ω; in that case, Ω is open if and only if Ω\{(1, 0, 0)} is open in ℝ and ϕ(Ω\{(1, 0, 0)} × ℝ) ∪ {(1, 0, 0)} is an open of S^{2} containing (1, 0, 0); the latter fact is possible if and only if Ω\{(1, 0, 0)} = ℝ (otherwise, if there existed x ∈ ℝ\(Ω\{(1, 0, 0)}), then the straight line ϕ({x} × ℝ) would tend to (1, 0, 0) and would not belong to the inverse image of Ω).

As conclusion, X is the topological space having the disjoint sum ℝ ⊔ {(1, 0, 0)} as underlying set, and a subset Ω of X is open if and only if Ω is an open of ℝ or Ω = X. In particular, the topological space X is not weak Hausdorff.

Now the topological space w(X) must be determined. It is known that there exists a natural bijection of sets Top(w(X), Y) ≅ kTop(X, Y) for any compactly generated topological space Y. Let f : X ⟶ Y be a continuous map. If Y = {f((1, 0, 0))}, then f is a constant map. Otherwise, there exists y ≠ f((1, 0, 0)) in Y. The singleton {y} is closed in Y since the topological space Y is compactly generated. So Y \{y} is an open of Y containing f((1, 0, 0)). Therefore f^{−1}(Y \{y}) is an open of X containing (1, 0, 0). So one deduces the equality f^{−1}(Y \{y}) = X, or equivalently one deduces that y ∉ f(X) for any y ≠ f((1, 0, 0)). This implies again that f is the constant map f = f((1, 0, 0)). Thus kTop(X, Y) ≅ Top({(1, 0, 0)}, Y). The proof is complete thanks to Yoneda’s Lemma.

Corollary 4.4. ℙ^{−}X = S^{2} ⊔ {0} and ℙ^{−}Y = {(1, 0, 0)} ⊔ ℝ.

Proof of Theorem 4.1. It suffices to prove that there exists a weak S-homotopy equivalence f of flows X ⟶ Y. Take the identity of {α, β, γ} on the 0-skeleton. Take the identity of S^{2} for the restriction f : ℙ_{α,γ}X ⟶ ℙ_{α,γ}Y. Let (u, v) ∈ ℝ × ℝ such that ϕ(u, v) = (0, 0, 1). Then it suffices to put f(0) = u for 0 ∈ ℙ_{α,β}X and f(0) = v for 0 ∈ ℙ_{β,γ}X.

The reader must not be surprised by the result of this section. Indeed, the branching space is given by a colimit. And it is well-known that colimits are badly behaved with respect to weak equivalences and that they must be replaced by homotopy colimits in algebraic topology.

5. The homotopy branching space

Let us denote by Q the cofibrant replacement functor of any model structure.

Definition 5.1. [11] [10] [3] An object X of a model category C is cofibrant (resp. fibrant) if and only if the canonical morphism ∅ ⟶ X from the initial object of C to X (resp. the canonical morphism X ⟶ 1 from X to the final object 1) is a cofibration (resp. a fibration).

In particular, in any model category, the canonical morphism ∅ ⟶ X where ∅ is the initial object) functorially factors as a composite ∅ ⟶ Q(X) ⟶ X of a cofibration ∅ ⟶ Q(X) followed by a trivial fibration Q(X) ⟶ X.

Proposition and Definition 5.2. [11] [10] [3] A Quillen adjunction is a pair of adjoint functors F : C ⇄ D : G between the model categories C and D such that one of the following equivalent properties holds:

1. if f is a cofibration (resp. a trivial cofibration), then so is F (f)

2. if g is a fibration (resp. a trivial fibration), then so is G(g).

One says that F is a left Quillen functor. One says that G is a right Quillen functor. Moreover, any left Quillen functor preserves weak equivalences between cofibrant objects and any right Quillen functor preserves weak equivalences between fibrant objects.

The fundamental tool of this section is the:

Theorem 5.3. [4] There exists one and only one model structure on Flow such that

1. the weak equivalences are the so-called weak S-homotopy equivalences, that is the morphisms of flows f : X ⟶ Y such that f^{0} : X^{0} ⟶ Y^{0} is a bijection and such that ℙf : ℙX ⟶ ℙY is a weak homotopy equivalence of topological spaces

2. the fibrations are the morphisms of flows f : X ⟶ Y such that ℙf : ℙX ⟶ ℙY is a (Serre) fibration of topological spaces.

Any flow is fibrant for this model structure.

Definition 5.4. [4] The notion of homotopy between cofibrant-fibrant flows is called S-homotopy.

Theorem 5.5. The branching space functor ℙ^{−} : Flow ⟶ Top is a left Quillen functor.

Proof. One has to prove that there exists a functor C^{−} : Top ⟶ Flow such that the pair of functors ℙ^{−} : Flow ⇄ Top : C^{−} is a Quillen adjunction.

Let us define the functor C^{−} : Top ⟶ Flow as follows: C^{−}(Z)^{0} = {0}, ℙC^{−}(Z) = Z with the composition law pr_{1} : (z_{1}, z_{2}) ↦ z_{1}. Indeed, one has pr_{1}(pr_{1}(z_{1}, z_{2}), z_{3}) = pr_{1}(z_{1}, pr_{1}(z_{2}, z_{3})) = z_{1}.

A continuous map f : ℙ^{−}X ⟶ Z gives rise to a continuous map f ∘h^{−} : ℙX ⟶ Z such that

f(h^{−}(x ∗ y)) = f(h^{−}(x)) = pr_{1}(f(h^{−}(x)), f(h^{−}(y)))

which provides the set map

Top(ℙ^{−}X, Z) ⟶ Flow(X, C^{−}(Z)).

Conversely, if g ∈ Flow(X, C^{−}(Z)), then ℙg : ℙX ⟶ ℙC^{−}(Z) = Z satisfies

ℙg(x ∗ y) = pr_{1}(ℙg(x), ℙg(y)) = ℙg(x).

Therefore ℙg factors uniquely as a composite ℙX ⟶ ℙ^{−}X ⟶ Z by Proposition 3.1. So one has the natural isomorphism of sets

Top(ℙ^{−}X, Z) ≅ Flow(X, C^{−}(Z)).

A morphism of flows f : X ⟶ Y is a fibration if and only if ℙf : ℙX ⟶ ℙY is a fibration by Theorem 5.3. Therefore C^{−} is a right Quillen functor and ℙ^{−} is a left Quillen functor by Proposition 5.2.

Definition 5.6. The homotopy branching space hoℙ^{−} X of a flow X is by definition the topological space ℙ^{−}Q(X). If α ∈ X^{0}, let hoℙ_{α}^{−} X = ℙ_{α}^{−}Q(X).

Corollary 5.7. Let f : X ⟶ Y be a weak S-homotopy equivalence of flows. Then hoℙ^{−} f : hoℙ^{−} X ⟶ hoℙ^{−} Y is a homotopy equivalence between cofibrant topological spaces.

Proof. The morphism of flows Q(f) is a weak S-homotopy equivalence between cofibrant flows. Since ℙ^{−} is a left Quillen adjoint, the morphism hoℙ^{−} f : hoℙ^{−} X ⟶ hoℙ^{−} Y is then a weak homotopy equivalence between cofibrant topological spaces, and therefore a homotopy equivalence by Whitehead’s theorem.

Corollary 5.8. Let X be a diagram of flows. Then there exists an isomorphism of flows \underrightarrow{lim} ℙ^{−}(X) ≅ ℙ^{−}(\underrightarrow{lim} X) where \underrightarrow{lim} is the colimit functor and there exists a homotopy equivalence between the cofibrant topological spaces \underrightarrow{holim} hoℙ^{−}(X) and hoℙ^{−}(\underrightarrow{holim} X) where \underrightarrow{holim} is the homotopy colimit functor.

The reader does not need to know what a general homotopy colimit is because Corollary 5.8 will be used only for homotopy pushout. And a definition of the latter is recalled in Section 8. Corollary 5.8 is the homotopic analog of the well-known fact of category theory saying that a left adjoint commutes with any colimit.

6. Construction of the branching homology and weak S-ho-motopy

In this section, we construct the branching homology of a flow and we prove that it is invariant with respect to weak S-homotopy equivalences (cf. Theorem 5.3).

Definition 6.1. Let X be a flow. Then the (n + 1)-th branching homology group H_{n+1}^{−}(X) is defined as the n-th homology group of the augmented simplicial set N_{∗}^{−}(X) defined as follows:

1. N_{n}^{−}(X) = Sing_{n}(hoℙ^{−} X) for n ⩾ 0

2. N_{−1}^{−}(X) = X^{0}

3. the augmentation map ϵ : Sing_{0}(hoℙ^{−} X) ⟶ X^{0} is induced by the mapping γ ↦ s(γ) from hoℙ^{−} X = Sing_{0}(hoℙ^{−} X) to X^{0}

where Sing(Z) denotes the singular simplicial nerve of a given topological space Z [7]. In other terms,

1. for n ⩾ 1, H_{n+1}^{−}(X) := H_{n}(hoℙ^{−} X)

2. H_{1}^{−}(X) := ker(ϵ)/ im (∂ : N_{1}^{−}(X) → N_{0}^{−}(X))

3. H_{0}^{−}(X) := ℤ(X^{0})/ im(ϵ).

where ∂ is the simplicial differential map, where ker(f) is the kernel of f and where im(f) is the image of f.

Proposition 6.2. For any flow X, H_{0}^{−}(X) is the free abelian group generated by the final states of X.

Proof. Obvious.

Let us denote by H̃_{∗}(Z) the reduced homology of a topological space Z, that is the homology group of the augmented simplicial nerve Sing(Z) ⟶ {0} (cf. for instance [16] definition p. 102). Then one has:

Proposition 6.3. For any flow X, there exists a natural isomorphism of abelian groups

H_{n+1}^{−}(X) ≅ ⨁_{α∈X^{0}} H̃_{n}(hoℙ_{α}^{−} X)

for any n ⩾ 0.

Proof. For n ⩾ 1, one has

⨁_{α∈X^{0}} H̃_{n}(hoℙ_{α}^{−} X) ≅ ⨁_{α∈X^{0}} H_{n}(hoℙ_{α}^{−} X) ≅ H_{n} ( ⨁_{α∈X^{0}} hoℙ_{α}^{−} X)

hence the result for n ⩾ 1 by Definition 6.1 and the X^{0}-grading of hoℙ^{−} X. For n = 0, this is a straightforward consequence of Definition 6.1 and of the definition of the homology of an augmented simplicial set.

Figure 3: Simplest example of T-homotopy equivalence

Proposition 6.4. Let f : X ⟶ Y be a weak S-homotopy equivalence of flows. Then N^{−}(f) : N^{−}(X) ⟶ N^{−}(Y) is a homotopy equivalence of augmented simplicial nerves.

Proof. This is a consequence of Corollary 5.7 and of the fact that the singular nerve functor is a right Quillen functor.

Corollary 6.5. Let f : X ⟶ Y be a weak S-homotopy equivalence of flows. Then H_{n}^{−}(f) : H_{n}^{−}(X) ⟶ H_{n}^{−}(Y) is an isomorphism for any n ⩾ 0.

7. Branching homology and T-homotopy

In this section, we prove that the branching homology is invariant with respect to T-homotopy equivalences (cf. Definition 7.3).

The most elementary example of T-homotopy equivalence which is not inverted by the model structure of Theorem 5.3 is the unique morphism ϕ dividing a directed segment in a composition of two directed segments (Figure 3 and Notation 7.1)

Notation 7.1. The morphism of flows ϕ : \overrightarrow{I} ⟶ \overrightarrow{I} ∗ \overrightarrow{I} is the unique morphism ϕ : \overrightarrow{I} ⟶ \overrightarrow{I}∗\overrightarrow{I} such that ϕ([0, 1]) = [0, 1]∗[0, 1] where the flow \overrightarrow{I} = Glob(\{[0, 1]\}) is the directed segment. It corresponds to Figure 3.

Definition 7.2. Let X be a flow. Let A and B be two subsets of X^{0}. One says that A is surrounded by B (in X) if for any α ∈ A, either α ∈ B or there exists execution paths γ_{1} and γ_{2} of ℙX such that s(γ_{1}) ∈ B, t(γ_{1}) = s(γ_{2}) = α and t(γ_{2}) ∈ B. We denote this situation by A ≪ B.

Definition 7.3. [5] A morphism of flows f : X ⟶ Y is a T-homotopy equivalence if and only if the following conditions are satisfied :

1. The morphism of flows f : X ⟶ Y ↾_{(f(X^{0})} is an isomorphism of flows. In particular, the set map f^{0} : X^{0} ⟶ Y^{0} is one-to-one.

2. For α ∈ Y^{0}\f(X^{0}), the topological spaces ℙ_{α}^{−}Y and ℙ_{α}^{+}Y (cf. Proposition A.1 and Definition A.2) are singletons.

3. Y^{0} ≪ f(X^{0}).

Proposition 7.4. Let f : X ⟶ Y be a T-homotopy equivalence. Then for any n ⩾ 0, the linear map H_{n}^{−}(f) : H_{n}^{−}(X) ⟶ H_{n}^{−}(Y) is an isomorphism.

Proof. For any α ∈ X^{0}, the continuous map hoℙ_{α}^{−} X ⟶ hoℙ_{α}^{−} Y is a weak homotopy equivalence. So for n ⩾ 1, one has

H_{n+1}^{−}(X) ≅ H_{n}(hoℙ^{−} X) ≅ ⨁_{α∈X^{0}} H_{n}(hoℙ_{α}^{−} X) ≅ ⨁_{α∈Y^{0}} H_{n}(hoℙ_{α}^{−} Y) ≅ H_{n+1}^{−}(Y)

since for α ∈ Y^{0}\f(X^{0}), the ℤ-module H_{n}(hoℙ_{α}^{−} Y) vanishes.

The augmented simplicial set N_{∗}^{−}(X) is clearly X^{0}-graded. So the branching homology is X^{0}-graded as well. Thus one has

H_{1}^{−}(X) = ⨁_{α∈X^{0}} G^{α}H_{1}^{−}(X)

with

G^{α}H_{1}^{−}(X) ≅
ker (Sing_{0}(hoℙ_{α}^{−} X) → ℤ{α}) / im (ℤ Sing_{1}(hoℙ_{α}^{−} X) → ℤ Sing_{0}(hoℙ_{α}^{−} X)) .

So one has the short exact sequences

0 → G^{α}H_{1}^{−}(X) → H_{0}(hoℙ_{α}^{−} X) → ℤ hoℙ_{α}^{−} X/ ker(s) → 0

for α running over X^{0}. If α ∈ Y^{0}\f(X^{0}), then H_{0}(hoℙ_{α}^{−} Y) = ℤ. In this case, s : hoℙ_{α}^{−} Y ⟶ {α} so ℤ hoℙ_{α}^{−} Y/ ker(s) ≅ ℤ. Therefore G^{α}H_{1}^{−}(Y) = 0.

At last, if α ∈ Y^{0}\f(X^{0}), then α belongs to im(s) because Y^{0} ≪ f(X^{0}). Hence the result.

Corollary 7.5. The branching homology is a dihomotopy invariant.

Proof. There are two kinds of dihomotopy equivalences in the framework of flows: the weak S-homotopy equivalences and the T-homotopy equivalences [5]. This corollary is then a consequence of Corollary 6.5 and Proposition 7.4.

The reader maybe is wondering why the singular homology of the homotopy branching space is not taken as definition of the branching homology.

Proposition 7.6. The functor X ↦ H_{0}(hoℙ^{−} X) is invariant with respect to weak S-homotopy, but not with respect to T-homotopy equivalences.

Proof. The first part of the statement is a consequence of Corollary 5.7. For the second part of the statement, let us consider the morphism of flows ϕ : \overrightarrow{I} ⟶ \overrightarrow{I}∗\overrightarrow{I} dividing the directed segment in two directed segments. Then H_{0}(hoℙ^{−} \overrightarrow{I}) = ℤ (the path-connected components of ℙ\overrightarrow{I} = \{u\}) and H_{0}(hoℙ^{−}(\overrightarrow{I} ∗ \overrightarrow{I})) = ℤ ⊕ ℤ (the path-connected components of ℙ^{−}(\overrightarrow{I} ∗ \overrightarrow{I}) = \{v = v ∗ w, w\}).

8. Long exact sequence for higher dimensional branchings

Lemma 8.1. One has:

1. if

[figure: U; V; W; X]

is a pushout diagram of topological spaces, then

[figure: Glob(U); Glob(V); Glob(W); Glob(X)]

is a pushout diagram of flows

2. if g : U ⟶ V is a cofibration of topological spaces, then Glob(g) : Glob(U) ⟶ Glob(V) is a cofibration of flows

3. if U is a cofibrant topological space, then Glob(U) is a cofibrant flow

4. there exists a cofibrant replacement functor Q of Top such that Q(Glob(U)) = Glob(Q(U)) for any topological space U.

Proof. The diagram of sets

\xymatrix{\{0, 1\} = Glob(U)^{0} \ar[r] \ar[d] & \{0, 1\} = Glob(V)^{0} \ar[d] \\ \{0, 1\} = Glob(W)^{0} \ar[r] & \{0, 1\} = Glob(X)^{0}}

is a square of constant set maps. Therefore the corresponding pushout of globes does not create any new non-constant execution paths. Hence the first assertion.

If g : U ⟶ V is a cofibration of topological spaces, then g is a retract of a transfinite composition of pushouts of morphisms of I = {S^{n−1} ⊂ D^{n}, n ⩾ 0}, and therefore Glob(g) is a retract of a transfinite composition of pushouts of morphisms of {Glob(S^{n−1}) ⊂ Glob(D^{n}), n ⩾ 0}. Since the model structure of Theorem 5.3 is cofibrantly generated with set of generating cofibrations I_{+}^{gl} = {Glob(S^{n−1}) ⊂ Glob(D^{n}), n ⩾ 0} ∪ {R, C} where R : {0, 1} ⟶ {0} and C : ∅ ⟶ {0}, the morphism of flows Glob(g) : Glob(U) ⟶ Glob(V) is a cofibration of flows. Hence the second assertion.

The third assertion is a consequence of the second one and of the fact that C : ∅ ⟶ {0} is a cofibration.

The cofibrant replacement functor Q of Flow is obtained by applying the small object argument for I_{+}^{gl} with the cardinal 2^{ℵ_{0}} ([4] Proposition 11.5). Let X be a flow. Let X : 2^{ℵ_{0}} ⟶ Flow be the 2^{ℵ_{0}}-sequence with X^{0} = ∅ and for any ordinal λ < 2^{ℵ_{0}} by the pushout diagram

[figure: ⨆_{k∈K} C_{k}; X^{λ}; ⨆_{k∈K} D_{k}; X^{λ+1}; ⨆_{k∈K} D_{k}; X]

where K is the set of morphisms (i.e. of commutative squares) from a morphism of I_{+}^{gl} to the morphism X^{λ} ⟶ X. Then Q(X) = X^{2^{ℵ_{0}}} . Pick a topological space U and consider X = Glob(U). Let X^{0} = ∅. Then X^{1} = {0} ⊔ {1} = Glob(∅). Let U^{0} = ∅. Let U : 2^{ℵ_{0}} ⟶ Top be the 2^{ℵ_{0}}-sequence giving the cofibrant replacement functor of the topological space U obtained by applying the small object argument for I = {S^{n−1} ⊂ D^{n}, n ⩾ 0} with the cardinal 2^{ℵ_{0}} (the cardinal ℵ_{0} is sufficient to obtain a cofibrant replacement functor in Top). Then an easy transfinite induction proves that Glob(U^{λ}) = X^{λ+1}. So Glob(U^{2^{ℵ_{0}}} ) = Q(X). The proof of the last assertion is complete because the functor U ↦ U^{2^{ℵ_{0}}} is a cofibrant replacement functor of Top since 2^{ℵ_{0}} ⩾ ℵ_{0}.

Lemma 8.2. (Calculating a homotopy pushout) In a model category M, the homotopy pushout of the diagram

\xymatrix{A \ar[r]^{i} \ar[d] & B \\ C}

is homotopy equivalent to the pushout of the diagram

\xymatrix{Q(A) \ar[r] \ar[d] & Q(B) \\ Q(C)}

where Q is a cofibrant replacement functor of M.

Proof. Consider the three-object category B

\xymatrix{1 \ar[r] \ar[d] & 2 \\ 0}

Let M^{B} be the category of diagrams of objects of M based on the category B, or in other terms the category of functors from B to M. There exists a model structure on M^{B} such that the colimit functor \underrightarrow{lim} : M^{B} ⟶ M is a left Quillen functor and such that the cofibrant objects are the functors F : B ⟶ C such that F (0), F (1) and F (2) are cofibrant in C and such that F (1 ⟶ 2) is a cofibration of M: cf. the proof of the Cube Lemma [11] [10]. Hence the result.

Definition 8.3. Let f : X ⟶ Y be a morphism of flows. The cone Cf of f is the homotopy pushout in the category of flows

\xymatrix{X \ar[r]^{f} \ar[d] & Y \ar[d] \\ 1 \ar[r] & Cf}

where 1 is the terminal flow.

Notation 8.4. Let Z be a topological space. Let us denote by \underline{L}(Z) the pushout

\xymatrix{\{0, 1\} \ar[d]_{R} \ar[r] & Glob(Z) \ar[d] \\ \{0\} \ar[r] & \underline{L}(Z)}

The 0-skeleton of \underline{L}(Z) is \{0\} and the path space of \underline{L}(Z) is Z ⊔ (Z × Z) ⊔ (Z × Z × Z) ⊔ . . ..

Lemma 8.5. Let g : U ⟶ V be a cofibration between cofibrant topological spaces. Then the cone of Glob(g) : Glob(U) ⟶ Glob(V) is S-homotopy equivalent to \underline{L}(V/U).

Proof. The diagram of flows

\xymatrix{Q(Glob(U)) \ar[d] \ar[r] & Q(Glob(V)) \\ Q(1)}

induces the diagram of topological spaces

\xymatrix{ℙQ(Glob(U)) \ar[d] \ar[r] & ℙQ(Glob(V)) \\ ℙQ(1)}

By Lemma 8.1, one can suppose that Q(Glob(U)) = Glob(Q(U)) and Q(Glob(V)) = Glob(Q(V)). Hence one can consider the pushout diagram of cofibrant topological spaces

[figure: Q(U); Q(g); Q(V); ℙQ(1); Z]

By Lemma 8.2, the topological space Z is cofibrant and is homotopy equivalent to the cone of g, that is V/U. Since Q(1)^{0} = {0}, one deduces the pushout diagram of flows

[figure: Q(Glob(U)); Q(Glob(V)); Q(1); \underline{L}(Z)]

Again by Lemma 8.2, and because Glob(g) is a cofibration of flows, the flow \underline{L}(Z) is cofibrant and S-homotopy equivalent to the cone of Glob(g). It then suffices to observe that the flows \underline{L}(Z) and \underline{L}(V/U) are S-homotopy equivalent to complete the proof.

Lemma 8.6. The homotopy branching space of the terminal flow is contractible.

Proof. Consider the homotopy pushout of flows

\xymatrix{Glob(U) \ar[r]^{Glob(g)} \ar[d] & Glob(V) \ar[d] \\ 1 \ar[r] & \underline{L}(V/U)}

where g : U ⟶ V is a cofibration between cofibrant topological spaces. The functor hoℙ^{−} preserves homotopy pushouts by Corollary 5.8. Therefore one obtains the homotopy pushout of topological spaces

\xymatrix{hoℙ^{−} Glob(U) \ar[r] \ar[d] & hoℙ^{−} Glob(V) \ar[d] \\ _{hoℙ_{−} 1} \ar[r] & hoℙ^{−} \underline{L}(V/U)}

Since U is cofibrant, Glob(U) is cofibrant as well, therefore Q(Glob(U)) is Shomotopy equivalent to Glob(U). So the space hoℙ^{−} Glob(U) = ℙ^{−}Q(Glob(U)) is homotopy equivalent to ℙ^{−}Q(Glob(U)) = U. Since V/U is a cofibrant space as well, the topological space

ℙ\underline{L}(V/U) ≅ V/U ⊔ (V/U × V/U) ⊔ (V/U × V/U × V/U) × …

is cofibrant as well. So hoℙ^{−} \underline{L}(V/U) is homotopy equivalent to V/U. One obtains the homotopy pushout of topological spaces

\xymatrix{U \ar[r]^{g} \ar[d] & V \ar[d] \\ _{hoℙ_{−} 1} \ar[r] & V/U}

for any cofibration g : U ⟶ V between cofibrant spaces. Take for g the identity of {0}. One deduces that hoℙ^{−} 1 is homotopy equivalent to V/U, that is to say a point.

Lemma 8.7. Let f : X ⟶ Y be a morphism of flows. Let Cf be the cone of f. Then the homotopy branching space hoℙ^{−}(Cf) of Cf is homotopy equivalent to the cone C(hoℙ^{−} f) of hoℙ^{−} f : hoℙ^{−} X ⟶ hoℙ^{−} Y.

Proof. Consider the homotopy pushout of flows

\xymatrix{X \ar[r]^{f} \ar[d] & Y \ar[d] \\ 1 \ar[r] & Cf}

Using Corollary 5.8, one obtains the homotopy pushout of topological spaces

\xymatrix{hoℙ^{−} X \ar[r]^{hoℙ^{−} f} \ar[d] & hoℙ^{−} Y \ar[d] \\ _{hoℙ_{−} 1} \ar[r] & hoℙ^{−} Cf}

The proof is complete with Lemma 8.6.

Theorem 8.8. (Long exact sequence for higher dimensional branchings) For any morphism of flows f : X ⟶ Y, one has the long exact sequence

⋯ → H_{n}^{−}(X) → H_{n}^{−}(Y) → H_{n}^{−}(Cf) → …
⋯ → H_{3}^{−}(X) → H_{3}^{−}(Y) → H_{3}^{−}(Cf) →
H_{2}^{−}(X) → H_{2}^{−}(Y) → H_{2}^{−}(Cf) →
H_{0}(hoℙ^{−} X) → H_{0}(hoℙ^{−} Y) → H_{0}(hoℙ^{−} Cf) → 0.

Proof. If g : U → V is a continuous map, then it is well-known that there exists a long exact sequence

⋯ → H_{∗}(U) → H_{∗}(V) → H_{∗}(Cg) → H_{∗−1}(U) →
⋯ → H_{0}(U) → H_{0}(V) → H_{0}(Cg) → 0

(cf. [16]). The theorem is then a corollary of Lemma 8.7.

9. Examples of calculation

Proposition 9.1. If X is a cofibrant flow, then the homotopy branching space hoℙ^{−} X and ℙ^{−}X are homotopy equivalent.

Proof. The functorial weak S-homotopy equivalence Q(X) ⟶ X between cofibrant flows becomes a homotopy equivalence ℙ^{−}Q(X) ⟶ ℙ^{−}X of cofibrant topological spaces since the functor ℙ^{−} is a left Quillen functor.

Since all examples given in this section are cofibrant flows, one can then replace their homotopy branching space by their branching space.

Figure 4: 1-dimensional branching

Figure 5: 2-dimensional branching

Figure 6: The Swiss Flag Example 1. The directed segment

By definition, the directed segment is the flow

\overrightarrow{I} = Glob(\{[0, 1]\}).

One has ℙ_{0}^{−}(\overrightarrow{I}) = \{[0, 1]\} and ℙ_{1}^{−}(\overrightarrow{I}) = ∅. And H_{n}^{−}(\overrightarrow{I}) = 0 for n ⩾ 1 and H_{0}^{−}(\overrightarrow{I}) = ℤ\{0, 1\}/s(ℙ_{0}^{−}(\overrightarrow{I})) is generated by the unique final state of \overrightarrow{I}.

2. 1-dimensional branching Consider the flow X defined by X^{0} = {0, 1, 2, 3} and ℙ_{0,1}X = {[0, 1]}, ℙ_{1,2}X =

{[1, 2]}, ℙ_{0,3}X = {[0, 3]}, ℙ_{0,2}X = {[0, 2]} and ℙ_{αβ}X = ∅ otherwise (cf. Figure 4).

Then ℙ_{0}^{−}X = {[0, 1], [0, 3]}, ℙ_{1}^{−}X = {[1, 2]} and ℙ_{2}^{−}X = ℙ_{3}^{−}X = ∅. One has H_{n}^{−}(X) = 0 for n ⩾ 2, H_{1}^{−}(X) = ℤ (generated by [0, 3]−[0, 1]), and H_{0}^{−}(X) = ℤ⊕ℤ (generated by the final states 2 and 3).

3. 2-dimensional branching Let us consider now the case of Figure 5. One has H_{1}^{−} = 0 and H_{n}^{−} = 0 for

n ⩾ 2. And H_{1}^{−} = ℤ, the generating branching being the one corresponding to the alternate sum (A) − (F) + (I). At last, H_{0}^{−} = ℤ ⊕ ℤ ⊕ Z, the generators being the final states of the three squares (C), (G) and (L). If α is the common initial state of (A), (F) and (I), then ℙ_{α}^{−} = S^{1}.

4. The Swiss Flag example 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 flow SW^{1} is obtained from SW^{0} by attaching a copy of Glob(D^{0}) to each pair (x, y) ∈ S with x ∈ SW^{0} identified with 0 and y ∈ SW^{0} identified with 1. The flow 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 Glob(D^{1}) 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 Glob(S^{0}) (there is not a unique choice to do that). Let SW = SW^{2} (cf. Figure 6 where the bold dots represent the points of the 0-skeleton). The flow SW represents the PV diagram of Figure 6.

The topological space ℙ_{α}^{−} is contractible for α ∈ SW^{0}\{(1, 2), (2, 1), (5, 5)}. And ℙ_{(5,5)}^{−} = ∅, ℙ_{(1,2)}^{−} = {u, v} and ℙ_{(2,1)}^{−} = {x, y} with s(u) = s(v) = (1, 2), t(u) = (2, 2), t(v) = (1, 3), s(x) = s(y) = (2, 1), t(x) = (3, 1) and t(y) = (2, 2).

Then H_{0}^{−} = ℤ (generated by the final state (5, 5)), H_{1}^{−} = ℤ ⊕ ℤ (generated by u − v and x − y). And H_{n}^{−} = 0 for any n ⩾ 2.

10. Conclusion

The branching homology is a dihomotopy invariant containing in dimension 0 the final states and in dimension n ⩾ 1 the non-deterministic n-dimensional branching areas of non-constant execution paths. The merging homology is a dihomotopy invariant containing in dimension 0 the initial states and in dimension n ⩾ 1 the nondeterministic n-dimensional merging areas of non-constant execution paths. The non-deterministic branchings and mergings of dimension n ⩾ 2 satisfies a long exact sequence which can be helpful for future applications or theoretical developments.

A. The case of mergings

Some definitions and results about mergings are collected here, almost without any comment or proof.

Proposition A.1. Let X be a flow. There exists a topological space ℙ^{+}X unique up to homeomorphism and a continuous map h^{+} : ℙX ⟶ ℙ^{+}X satisfying the following universal property:

1. For any x and y in ℙX such that t(x) = s(y), the equality h^{+}(y) = h^{+}(x ∗ y) holds.

2. Let ϕ : ℙX ⟶ Y be a continuous map such that for any x and y of ℙX such that t(x) = s(y), the equality ϕ(y) = ϕ(x ∗ y) holds. Then there exists a unique continuous map \overline{ϕ} : ℙ^{+}X ⟶ Y such that ϕ = \overline{ϕ} ∘ h^{+}.

Moreover, one has the homeomorphism

ℙ^{+}X ≅ ⨆_{α∈X^{0}} ℙ_{α}^{+}X

where ℙ_{α}^{+}X := h^{+} (⨆_{β∈X^{0}} ℙ_{α,β}^{+}X). The mapping X ↦ ℙ^{+}X yields a functor ℙ^{+} from Flow to Top.

Loosely speaking, the merging space of a flow is the space of germs of nonconstant execution paths ending in the same way.

Definition A.2. Let X be a flow. The topological space ℙ^{+}X is called the merging space of the flow X. The functor ℙ^{+} is called the merging space functor.

Notice by that considering the opposite X^{op} of a flow X (by interverting s and t), then one obtains the following obvious relation between ℙ^{−} and ℙ^{+} : ℙ^{+}X = ℙ^{−}X^{op} and ℙ^{−}X = ℙ^{+}X^{op}.

Theorem A.3. There exists a weak S-homotopy equivalence of flows f : X ⟶ Y such that the topological spaces ℙ^{+}X and ℙ^{+}Y are not weakly homotopy equivalent.

Theorem A.4. The merging space functor ℙ^{+} : Flow ⟶ Top is a left Quillen functor.

Definition A.5. The homotopy merging space hoℙ^{+} X of a flow X is by definition the topological space ℙ^{+}Q(X). If α ∈ X^{0}, let hoℙ_{α}^{+} X = ℙ_{α}^{+}X.

Corollary A.6. Let f : X ⟶ Y be a weak S-homotopy equivalence of flows. Then hoℙ^{+} f : hoℙ^{+} X ⟶ hoℙ^{+} Y is a homotopy equivalence between cofibrant topological spaces.

Definition A.7. Let X be a flow. Then the (n + 1)-th merging homology group H_{n+1}^{+}(X) is defined as the n-th homology group of the augmented simplicial set N_{∗}^{+}(X) defined as follows:

1. N_{n}^{+}(X) = Sing_{n}(hoℙ^{+} X) for n ⩾ 0

2. N_{−1}^{+}(X) = X^{0}

3. the augmentation map ϵ : Sing_{0}(hoℙ^{+} X) ⟶ X^{0} is induced by the mapping

γ ↦ s(γ) from hoℙ^{+} X = Sing_{0}(hoℙ^{+} X) to X^{0} where Sing(Z) denotes the singular simplicial nerve of a given topological space Z. In other terms,

1. for n ⩾ 1, H_{n+1}^{+}(X) := H_{n}(hoℙ^{+} X)

2. H_{1}^{+}(X) := ker(ϵ)/ im (∂ : N_{1}^{+}(X) → N_{0}^{+}(X))

3. H_{0}^{+}(X) := ℤ(X^{0})/ im(ϵ). where ∂ is the simplicial differential map, where ker(f) is the kernel of f and where im(f) is the kernel of f.

Proposition A.8. For any flow X, H_{0}^{+}(X) is the free abelian group generated by the initial states of X.

Proposition A.9. For any flow X, there exists a natural isomorphism of abelian groups

H_{n+1}^{+}(X) ≅ ⨁_{α∈X^{0}} H̃_{n}(hoℙ_{α}^{+} X)

for any n ⩾ 0.

Proposition A.10. Let f : X ⟶ Y be a weak S-homotopy equivalence of flows. Then N^{+}(f) : N^{+}(X) ⟶ N^{+}(Y) is a homotopy equivalence of augmented simplicial nerves.

Corollary A.11. Let f : X ⟶ Y be a weak S-homotopy equivalence of flows. Then H_{n}^{+}(f) : H_{n}^{+}(X) ⟶ H_{n}^{+}(Y) is an isomorphism for any n ⩾ 0.

Proposition A.12. Let f : X ⟶ Y be a T-homotopy equivalence. Then for any n ⩾ 0, the linear map H_{n}^{+}(f) : H_{n}^{+}(X) ⟶ H_{n}^{+}(Y) is an isomorphism.

Corollary A.13. The merging homology is a dihomotopy invariant.

Lemma A.14. The homotopy merging space of the terminal flow is contractible.

Lemma A.15. Let f : X ⟶ Y be a morphism of flows. Let Cf be the cone of f. Then the homotopy merging space hoℙ^{+}(Cf) of Cf is homotopy equivalent to the cone C(hoℙ^{+} f) of hoℙ^{+} f : hoℙ^{+} X ⟶ hoℙ^{+} Y.

Theorem A.16. (Long exact sequence for higher dimensional mergings) For any morphism of flows f : X ⟶ Y, one has the long exact sequence

⋯ → H_{n}^{+}(X) → H_{n}^{+}(Y) → H_{n}^{+}(Cf) → …
⋯ → H_{3}^{+}(X) → H_{3}^{+}(Y) → H_{3}^{+}(Cf) →
H_{2}^{+}(X) → H_{2}^{+}(Y) → H_{2}^{+}(Cf) →
H_{0}(hoℙ^{+} X) → H_{0}(hoℙ^{+} Y) → H_{0}(hoℙ^{+} Cf) → 0.

We conclude this section by an additional remark about the Quillen adjunctions induced by the functors ℙ^{−} and ℙ^{+}.

Theorem A.17. The Quillen adjunctions ℙ^{−} : Flow ⇄ Top : C^{−} and ℙ^{+} : Flow ⇄ Top : C^{+} together induce a Quillen adjunction ℙ^{−} ⊔ ℙ^{+} : Flow ⇄ Top : C^{−} × C^{+}.

Proof. Indeed, one has

Top(ℙ^{−}X ⊔ ℙ^{+}X, Z) ≅ Top(ℙ^{−}X, Z) × Top(ℙ^{+}X, Z)
≅ Flow(X, C^{−}Z) × Flow(X, C^{+}Z)
≅ Flow(X, C^{−}Z × C^{+}Z)

If Z ⟶ T is a fibration of topological spaces, then both C^{−}Z ⟶ C^{−}T and C^{+}Z ⟶ C^{+}T are fibrations of flows by Theorem 5.3. Since a product of fibrations is a fibration, then C^{−} × C^{+} is a right Quillen adjoint. And therefore ℙ^{−} ⊔ ℙ^{+} is a left Quillen adjoint.

None of the Quillen adjunctions ℙ^{−} : Flow ⇄ Top : C^{−}, ℙ^{+} : Flow ⇄ Top : C^{+} and ℙ^{−} ⊔ ℙ^{+} : Flow ⇄ Top : C^{−} × C^{+} gives rise to a Quillen equivalence. For obvious reasons, the geometry of the branching space, the merging space or both together cannot characterize a flow. Indeed, the information about how branchings and mergings are related to one another is missing.

B. Branching space, merging space and S-homotopy

The purpose of this section is to prove the:

Proposition B.1. Let X and Y be two S-homotopy equivalent flows (cf. Definition 5.4) which are not necessarily cofibrant. Then the topological spaces ℙ^{−}X and ℙ^{−}Y are homotopy equivalent.

Proposition B.1 is already proved if X and Y are both cofibrant: indeed since ℙ^{−} : Flow ⟶ Top is a left Quillen functor by Proposition 5.5, it preserves weak equivalences between cofibrant objects.

Recall that two morphisms of flows f, g : X ⟶ Y are S-homotopy equivalent if and only if there exists a continuous map H : [0, 1] ⟶ FLOW(X, Y) such that H(0) = f and H(1) = g where the space FLOW(X, Y) is the set Flow(X, Y) equipped with the Kelleyfication of the compact-open topology. In the same way, the space TOP(U, V) denotes the set Top(U, V) equipped with the Kelleyfication of the compact-open topology. In particular, one has the natural bijection of sets Top(U × V, W) ≅ Top(U, TOP(V, W)) for any topological space U, V and W.

We are going to need the category of non-contracting topological 1-categories.

Definition B.2. [4] A non-contracting topological 1-category X is a pair of compactly generated topological spaces (X^{0}, ℙX) together with continuous maps s, t and ∗ satisfying the same properties as in the definition of flow except that X^{0} is not necessarily discrete. The corresponding category is denoted by 1Cat_{1}^{top}.

Proposition B.3. [4] Let X and Y be two objects of 1Cat_{1}^{top}. There exists a unique structure of topological 1-category X ⊗ Y on the topological space X × Y such that

1. (X ⊗ Y)^{0} = X^{0} × Y^{0} .

2. ℙ (X ⊗ Y) = (ℙX × ℙX) ⊔ (X^{0} × ℙY ) ⊔ (ℙX × Y^{0}).

3. s (x, y) = (s(x), s(y)), t (x, y) = (t(x), t(y)), (x, y) ∗ (z, t) = (x ∗ z, y ∗ t).

Theorem B.4. [4] The tensor product of 1Cat_{1}^{top} is a closed symmetric monoidal structure, that is there exists a bifunctor

[1Cat_{1}^{top}] : 1Cat_{1}^{top} × 1Cat_{1}^{top} ⟶ 1Cat_{1}^{top}

contravariant with respect to the first argument and covariant with respect to the second argument such that one has the natural isomorphism of sets

1Cat_{1}^{top} (X ⊗ Y, Z) ≅ 1Cat_{1}^{top} (X, [1Cat_{1}^{top}] (Y, Z))

for any topological 1-categories X, Y and Z. Moreover, one has the natural homeomorphism

([1Cat_{1}^{top}] (Y, Z))^{0} ≅ FLOW(Y, Z).

With the tools above at hand, we can now prove the

Theorem B.5. The functor ℙ^{−} : Flow ⟶ Top induces a natural continuous map (ℙ^{−})_{∗} : FLOW(X, Y) ⟶ TOP(ℙ^{−}X, ℙ^{−}Y) for any flow X and Y.

Proof. The functor ℙ^{−} : Flow ⟶ Top yields a set map

FLOW(X, Y) ⟶ TOP(ℙ^{−}X, ℙ^{−}Y).

One has to prove that this set map is continuous.

By Yoneda’s lemma, one has an isomorphism between the set

Nat (Top (−, FLOW(X, Y)) , Top (−, TOP(ℙ^{−}X, ℙ^{−}Y)))

and the set

Top (FLOW(X, Y), TOP(ℙ^{−}X, ℙ^{−}Y))

where Nat(F, G) denotes the set of natural transformations from a functor F to another functor G.

Let U be a topological space. Then U can be viewed as a non-contracting topological 1-category if U is identified with its 0-skeleton. Then

Top (U, FLOW(X, Y)) ≅ Top (U, ([1Cat_{1}^{top}] (X, Y))^{0})
≅ 1Cat_{1}^{top} (U, [1Cat_{1}^{top}](X, Y))
≅ 1Cat_{1}^{top} (U ⊗ X, Y) .

Let ℙ^{−} : 1Cat_{1}^{top} ⟶ Top be the functor defined as follows: if X is an object of 1Cat_{1}^{top}, then the topological space ℙ^{−}X is the quotient of the topological space ℙX by the topological closure of the smallest equivalence relation identifying x and x ∗ y for any x, y ∈ ℙX such that t(x) = s(y). Clearly, one has the commutative diagram of functors

\xymatrix{Flow \ar[r]^{ℙ^{−}} \ar[d] & Top \ar[d]_{=} \\ 1Cat_{1}^{top} \ar[r]^{ℙ^{−}} & Top}

where the functor Flow ⟶ 1Cat_{1}^{top} is the canonical embedding.

The non-contracting topological 1-category U ⊗X looks as follows: the 0-skeleton is equal to U × X^{0} and the path space is equal to U × ℙX with the composition law characterized by s(u, x) = (u, sx), t(u, x) = (u, tx) and (u, x) ∗ (u, y) = (u, x ∗ y). Therefore there exists a natural homeomorphism ℙ^{−}(U ⊗ X) ≅ U × ℙ^{−}X. So the functor ℙ^{−} : 1Cat_{1}^{top} ⟶ Top induces a set map

1Cat_{1}^{top} (U ⊗ X, Y) ⟶ Top (U × ℙ^{−}X, ℙ^{−}Y )

Since Top (U × ℙ^{−}X, ℙ^{−}Y) ≅ Top (U, TOP (ℙ^{−}X, ℙ^{−}Y)), one obtains by composition a natural set map

Top (U, FLOW(X, Y)) ⟶ Top (U, TOP (ℙ^{−}X, ℙ^{−}Y ))

which by Yoneda’s lemma provides a continuous map

FLOW(X, Y) ⟶ TOP (ℙ^{−}X, ℙ^{−}Y )

whose underlying set map is exactly the set map Flow(X, Y) ⟶ Top (ℙ^{−}X, ℙ^{−}Y) induced by the functor ℙ^{−} : Flow ⟶ Top.

Corollary B.6. Let f and g be two S-homotopy equivalent morphisms of flows from X to Y. Then the continuous maps ℙ^{−}f and ℙ^{−}g from ℙ^{−}X to ℙ^{−}Y are homotopic.

Proof. Let H be an element of Top([0, 1], FLOW(X, Y)) such that H(0) = f and H(1) = g. Then (ℙ^{−})_{∗}(H) ∈ Top([0, 1], TOP(ℙ^{−}X, ℙ^{−}Y)) yields an homotopy from ℙ^{−}f to ℙ^{−}g.

Corollary B.7. Let X and Y be two S-homotopy equivalent flows. Then the topological spaces ℙ^{−}X and ℙ^{−}Y are homotopy equivalent.

Of course, the same theorem holds for the merging space functor:

Corollary B.8. Let X and Y be two S-homotopy equivalent flows. Then the topological spaces ℙ^{+}X and ℙ^{+}Y are homotopy equivalent.

References

[1] Brown, R., “Topology,” Ellis Horwood Ltd., Chichester, 1988, second edition, xviii + 460 pp.

[2] Bubenik, P., Context for models of concurrency, in: GETCO 2004 proceedings, 2004, to appear in BRICS.

[3] Dwyer, W. G. and J. Spaliński, Homotopy theories and model categoriesin: Handbook of algebraic topology, North-Holland, Amsterdam, 1995 pp. 73– 126.

[4] Gaucher, P., A model category for the homotopy theory of concurrency, Homology, Homotopy and Applications 5 (2003), pp. 549–599.

[5] Gaucher, P., Comparing globular complex and flow (2005), arXiv:math.AT/0308063, To appear in the New York Journal of Mathematics.

[6] Glabbeek, R., On the Expressiveness of Higher Dimensional Automata, in: EXPRESS 2004 proceedings, 2004.

[7] Goerss, P. G. and J. F. Jardine, “Simplicial homotopy theory,” Birkhäuser Verlag, Basel, 1999, xvi+510 pp.

[8] Goubault, E., Some geometric perspectives in concurrency theory, Homology, Homotopy and Applications 5 (2003), pp. 95–136.

[9] Grandis, M., Directed homotopy theory. I, Cah. Topol. Géom. Différ. Catég. 44 (2003), pp. 281–316.

[10] Hirschhorn, P. S., “Model categories and their localizations,” Mathematical Surveys and Monographs 99, American Mathematical Society, Providence, RI, 2003, xvi+457 pp.

[11] Hovey, M., “Model categories,” American Mathematical Society, Providence, RI, 1999, xii+209 pp.

[12] Lewis, L. G., “The stable category and generalized Thom spectra,” Ph.D. thesis, University of Chicago (1978).

[13] May, J. P., “A concise course in algebraic topology,” University of Chicago Press, Chicago, IL, 1999, x+243 pp.

[14] Pratt, V., Modeling concurrency with geometry, in: A. Press, editor, Proc. of the 18th ACM Symposium on Principles of Programming Languages, 1991.

[15] Quillen, D. G., “Homotopical algebra,” Springer-Verlag, Berlin, 1967, iv+156 pp.

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

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/2005/n1a4/v7n1a4.(dvi,ps,pdf)

Philippe Gaucher

gaucher@pps.jussieu.fr
http://www.pps.jussieu.fr/~gaucher/

Preuves Programmes et Systèmes Université Paris 7–Denis Diderot Case 7014 2 Place Jussieu 75251 PARIS Cedex 05 France