Homology, Homotopy and Applications, vol.5(2), 2003, pp.257–280

STATE SPACES AND DIPATHS UP TO DIHOMOTOPY

MARTIN RAUSSEN

(communicated by Gunnar Carlsson)

Abstract Geometric models have been used by several authors to describe the behaviour of concurrent sytems in computer science. A concurrent computation corresponds to an oriented path (dipath) in a (locally) partially ordered state space, and dihomotopic dipaths correspond to equivalent computations. This paper studies several invariants of the state space in the spirit of those of algebraic topology, but taking partial orders into account as an important part of the structure. We use several categories of fractions of the fundamental category of the state space and define and investigate the related quotient categories of “components”. For concurrency applications, the resulting categories can be interpreted as a dramatic reduction of the size of the state space to be considered.

1. Introduction

1.1. Background and history

The use of geometric models in the description of the behaviour of concurrent systems in computer science can be traced back at least to the work of E.W. Dijkstra [6], where concurrent processes are modeled by so-called progress graphs; cf. for instance Fig. 1. For so-called semaphore programs (explained below), these progress graphs have been exploited for an algorithmic determination of deadlocs and unreachable states [23, 5, 9]. A systematic framework for studying schedules of actions of distributed computations by means of geometric properties was proposed by V. Pratt [25] and subsequently R. van Glabbeek [30]. In his thesis [16], É. Goubault initiated a systematic study of Higher Dimensional Automata (HDA) built on cubical sets [27, 4, 3] employing methods from algebraic topology, in particular homological methods. The idea is that a schedule of actions (including deadlocks and unreachables, but also serializability conditions etc.) is essentially invariant under “continuous deformation”, i.e. some sort of homotopy. This point of view has been exploited in a database framework in [20] and later in [11].

Acknowledgements. The author wishes to thank the referee for several corrections to the original version of this paper as for suggestions improving the presentation. Thanks are also due to Laboratoire d’Informatique, École Polytechnique, Paris, for its hospitality while the final revision of this paper was undertaken. Received November 1, 2001, revised September 9, 2002; published on April 22, 2003. 2000 Mathematics Subject Classification: 51H15, 54E99. Key words and phrases: abstract homotopy theory, dihomotopy theory. \begin{matrix}c \\ ◯ \end{matrix} 2003, Martin Raussen. Permission to copy for private use granted.

Relevant models have to reflect the irreversibility of time, and this is why partial orders have to play an important role. A prototypical example (the “Swiss flag” in Fig. 1) models the concurrent execution of two programs (on the axes) both locking (P) and releasing (V) by a semaphore two shared objects a and b, but in reverse order. An execution path in this model has to be a “dipath”, i.e., a continuous path with monotone projection to each axis – modelling the progress of an individual program; moreover, it has to start at the minimal point (0, 0) and to end at the maximal point (1, 1), and it has to avoid the shaded forbidden region (“Swiss flag”) modelling concurrent access to a or b. A dipath entering the “unsafe” region cannot end up at (1, 1) – likewise, no dipath from (0, 0) can ever enter the “unreachable” region in Fig. 1. Moreover, there are two possible outcomes of a run of the concurrent program: Either T_{1} locks both a and b before T_{2} can access any of them, or T_{2} uses b and a before T_{1} does. These two runs correspond to dipaths that pass “under”, resp. ”over” the forbidden region, but without any further restrictions. The example suggests that (some sort of) homotopy can capture the essential difference between two dipaths or executions.

Figure 1: Example of a progress graph

1.2. Partial orders and dipaths

With the intention to employ topological methodology in this framework, we proposed [11] to use partially ordered topological spaces, cf. [24] for an early and detailed reference, or rather a local version, as a base for further analysis:

A topological space X with a partial order ⩽ is called a po-space if and only if the relation ⩽⊂ X × X is closed. A po-space is automatically Hausdorff [24].

The definition of a locally partially ordered space (for short lpo-space) formally resembles that of a manifold, using covers of a Hausdorff space X by open po-subsets such that the partial orders on those agree on suitable (po-)neighbourhoods of every element. Two local partial orders are equivalent if their union is still a local partial order. See [11] – slightly uncorrect in the preprint version – or [12] for details.

The structure preserving maps between lpo-spaces are the dimaps [11], i.e., continuous maps respecting partial orders within sufficiently small neighbourhoods of every point. The most important dimaps for our purposes are the dipaths: Let I⃗ := [0, 1] denote the unit interval and let R_{⩾0} := {t ∈ R|t ⩾ 0}, both equipped with the natural order; let X denote an lpo-space, and let x_{0}, x_{1} ∈ X. A dipath from x_{0} to x_{1} is a dimap f : I⃗ → X with f(0) = x_{0} and f(1) = x_{1}. An infinite dipath from x_{0} is a dimap f : R_{⩾0} → X with f(0) = x_{0} and such that lim_{t→∞} f(t) does not exist. Infinite dipaths model execution paths that run indefinitely without “dying slowly” (thus avoiding the so-called “zeno” executions) in forward semantics of concurrent programs. Analogous problems in backwards semantics can be handled likewise by considering infinite dipaths defined on R_{⩽0} = {t ∈ R|t ⩽ 0} or on R.

Higher Dimensional Automata (cf. Sect. 1.1) and their dynamics can be seen as particular lpo-spaces; executions of programs on these state spaces correspond to finite or infinite dipaths on those. Just recently, alternative frameworks for handling the properties of HDAs have been proposed and discussed. In particular, the flows of P. Gaucher[14] and the d-spaces of M. Grandis[18, 19] – many of them arising from lpo-spaces – admit nicer categorical and homotopy theoretical properties.

Classical concurrency uses mainly techniques of a combinatorial or graph theoretical nature. All of the approaches mentioned above have in common an attempt to employ topological techniques to enhance our understanding; these are in particular useful to model higher dimensional connections and relations.

1.3. Dihomotopy

To capture equivalent behaviour (ensuring the same results of computations etc.) along executions, V. Pratt [25] suggested to use “monoidal homotopies” as equivalence relation on spaces of executions. Examples of 3-dimensional progress graphs (cf. [11]) showed that it is not enough to consider standard homotopies between dipaths; instead, one has to modify the definition in a rather obvious way:

Definition 1.1. Let X denote an lpo-space with x_{0}, x_{1} ∈ X.

1. A dihomotopy from x_{0} to x_{1} is a continuous map H : I × I⃗ → X such that H_{s} = H(s, −) : I⃗ → X is a dipath from x_{0} to x_{1} for every s ∈ I. Two dipaths f, g : I⃗ → X from x_{0} to x_{1} are dihomotopic to each other if there exists a dihomotopy from x_{0} to x_{1} such that H_{0} = f and H_{1} = g. We denote by π⃗_{1}(X)(x_{0}, x_{1}) the set of dihomotopy (equivalence) classes of dipaths from x_{0} to x_{1}.

2. An infinite dihomotopy from x_{0} is a continuous map H : I × R_{⩾0} → X such that H_{(}s, −) : R_{⩾0} → X is an infinite dipath from x_{0} for every s ∈ I. We denote by π⃗_{1}(X)(x_{0}, ∞) the set of dihomotopy classes of infinite dipaths from x_{0}. Likewise, one defines π⃗_{1}(X)(−∞, x_{1}) and π⃗_{1}(X)(−∞, ∞).

Remark that the paths H(−, t), t ∈ I⃗, in general, are not directed. Otherwise, dihomotopy would not be an equivalence relation. It is quite obvious how to generalise these definitions from the dihomotopy of paths with fixed end points to the dihomotopy of dipaths with end points moving in specified subspaces X_{0} and X_{1} – yielding equivalence classes π⃗_{1}(X; X_{0}, X_{1}) – or to the dihomotopy of dimaps, cf. [11].

Concatenation on the level of dipaths factors over dihomotopy and induces compositions

π⃗_{1}(X)(x_{0}, x_{1}) × π⃗_{1}(X)(x_{1}, x_{2}) → π⃗_{1}(X)(x_{0}, x_{2}) and
π⃗_{1}(X)(x_{0}, x_{1}) × π⃗_{1}(X)(x_{1}, ∞) → π⃗_{1}(X)(x_{0}, ∞),
(f, g) ↦ g ∗ f,

satisfying the associativity conditions. In this paper g ∗ f means: “first f, then g”.

There is an alternative (“combinatorial”) approach to dihomotopy: An elementary dihomotopy in X is a dimap H : I⃗^{2} → X defined on the partially ordered square I⃗^{2}. The two dipaths H(1, t) ∗ H(s, 0) and H(s, 1) ∗ H(0, t) on the boundary of the square are then elementarily dihomotopic to each other. This relation is clearly reflexive and symmetric. It is not difficult to define concatenations of elementary dihomotopies with matching faces; in this context, we insist on directedness “horizontally”, whereas directions may shift “vertically”. The relation combinatorial dihomotopy is then defined as the transitive closure of the relation elementary dihomotopy.

Combinatorial dihomotopy is the relation suggested by concurrency models. The interpretation of an elementary dihomotopy is the independence of two transitions τ_{0} and τ_{1}, i.e., first τ_{0} and then τ_{1} is equivalent to first τ_{1} and then τ_{0}; moreover any interleaving of partial executions of these two transitions has to yield the same result.

Remark 1.2. It is clear, that an elementary dihomotopy is a particular dihomotopy which is directed along both parameters. As a consequence, combinatorial dihomotopy implies dihomotopy. A combinatorial dihomotopy is a dihomotopy with the special property that the paths H(−, t), t ∈ I⃗, are concatenations of actual dipaths and of dipaths “in the wrong direction” (zig-zags).

In general, dihomotopy does not imply combinatorial dihomotopy, as the following example shows: Let Σ⃗X denote the unreduced suspension of a topological space X with the partial order coming exclusively from the suspension coordinate. This is the po-space introduced in [15] – for different purposes – under the term Glob(X). All dipaths from the minimal to the maximal point have the form α_{x} : I → Σ⃗X, t ↦ [(x, t)] for a fixed x ∈ X – or are monotone reparametrizations of those. The dipaths α_{x} and α_{x′} from the bottom to the top cannot be connected by a combinatorial homotopy for x ≠ x′: For t ∉ ∂I, the only zig-zag paths connecting (x, t) and (x′, t) have to pass through the minimal or through the maximal point. Since the endpoints have to be kept fix, it is not possible to construct a continuous combinatorial dihomotopy between α_{x} and α_{x′}. On the other hand, these two dipaths are obviously dihomotopic in the sense of Def. 1.1 if just x and x′ are contained in the same path component of X.

There is evidence, that the two relations agree for “nice enough” po-spaces: L. Fajstrup has recently proved [8] that two dihomotopic dipaths in a cubical complex – the geometric realisation of a cubical set[4, 3] – are combinatorially dihomotopic as well.

1.4. Aims and Structure

The transition from (directed) topology to algebra is more complicated than in the classical situation, since the reverse of a dipath is no longer directed. Hence, dipaths up to dihomotopy neither form a fundamental group nor a fundamental groupoid. Instead, one has to work with fundamental categories. These are huge gadgets, and this paper searches for representations of the essential dihomotopy information in more compressed ways. To this aim, we propose to use categories of fractions of a fundamental category with respect to suitably chosen sytems of morphisms and to investigate quotient categories of those with objects the path components with respect to these systems.

In Sect. 2, we discuss the fundamental category of an lpo-space and of a related quotient category retaining only “globally relevant information”. Sect. 3 reviews the main tool, categories of fractions with respect to systems of morphisms, and proposes to investigate certain “component categories”. Sect. 4 describes and investigates several relevant systems of morphisms within a fundamental category and the associated component categories. In Sect. 5, we propose a similar scheme for an investigation of “higher dihomotopy”. Finally, Sect. 6 discusses the (lack of) naturality of the component categories.

The original stimulus for this study was the interesting paper [28] by S. Sokołowski who defined a functor Ω_{1} associating to a po-space a partial order on the dihomotopy classes of dipaths with given start point; moreover, he defined in that paper higher dimensional functors Ω_{n}. I would like to thank him and also L. Fajstrup and É. Goubault for many clarifying discussions.

2. The fundamental category and its relatives

2.1. The fundamental category

Let X denote an lpo-space or a d-space, cf. [18, 19], i.e., a topological space X with a specified set of dipaths within the path set P X including the constant paths, which is closed under concatenation and invariant under monotone reparameterizations. A d-space may have arbitrarily small loops; in particular, the dipaths do not give rise to a locally antisymmetric relation. The dihomotopy relation investigated by Grandis corresponds to our combinatorial dihomotopy.

Definition 2.1. 1. The objects of the fundamental category π⃗_{1}(X) are the points of X. The morphisms between elements x and y are given as the dihomotopy classes in π⃗_{1}(X)(x, y).

2. The category π_{1}^{∞}(X) contains π⃗_{1}(X). It has an additional maximal element ∞ with Mor(x, ∞) = π⃗_{1}(X)(x, ∞) for x ∈ X, Mor(∞, y) = ∅ for y ∈ X and Mor(∞, ∞) = 1_{∞}.

In both cases, composition of morphisms with matching target, resp. source is given by concatenation of dipaths – up to dihomotopy.

Compared to a fundamental group, a fundamental category is an enormous gadget and it has a much less nice algebraic structure. On the other hand, from simple examples one gets the impression, that the cardinality of the set of morphisms between two points is quite robust when these points are only perturbed a little bit:

Example 2.2. 1. For the square with one hole (left part of Fig. 2), there are no dipaths between the regions marked L and R, there is no dipath from T to any other region, neither is there a morphism from any other region to B. There are, up to dihomotopy, two dipaths from any point of B to any point of T. Moreover, from any point of B, certain points of B, L, R can be reached by (exactly one) dipath up to dihomotopy. Likewise, any point of T can be reached from (certain of) the points in L, R and T in essentially one way.

Figure 2: Square with a hole and complement of a ”Swiss flag”

2. For the complement of a “Swiss flag” (right part of Fig. 2), the situation is a bit more complicated: There is no dipath leaving the unsafe rectangle Us and there is no dipath entering the unreachable rectangle Ur from the outside. It is possible to reach Us by essentially one dipath from B ∪ Bl ∪ Br up to dihomotopy, and from Ur, one can reach points in Tl ∪ Tr ∪ T in essentially one way. The only possibility for two classes of dipaths between points occurs when the first is in B and the second in T. Moreover, these classes can be represented by dipaths along the boundary – representing the two sequential executions.

In general, it is not easy to calculate fundamental categories of an lpo-space or a d-space. For the spaces arising from 2-dimensional mutual exclusion models, tools for the calculation are contained in [26]. In a much more general direction, M. Grandis quite recently adapted the usual proof of the Seifert-van Kampen theorem to the case of d-spaces ([18], Thm. 3.6) exhibiting the fundamental category of a (suitable) union of subspaces as a pushout (in Cat) of the fundamental categories of the subspaces. With the result of L. Fajstrup (cf. Rem. 1.2), this theorem is also valid for the fundamental categories of cubical sets or complexes with dihomotopy as defined in Def. 1.1. It is still not quite clear though how to use this pasting theorem algorithmically to calculate fundamental categories for interesting classes of lpospaces.

2.2. Cancellation problems In general, cancellation is not possible in a fundamental category.

Example 2.3. Consider the po-space X = ∂I⃗^{3} \ int(I⃗^{2} × {0}) ⊂ R^{3}, the boundary of a standard cube from which the interior of the bottom face is removed. For x_{0} = (0, 0, 0) and x_{1} = (1, 1, z), the dihomotopy set π⃗_{1}(X)(x_{0}, x_{1}) consists of two elements for z < 1. They yield the unique element in π⃗_{1}(X)(x_{0}, (1, 1, 1)) after composition with a dipath class from x_{1} to (1, 1, 1).

One way to handle non-cancellation is to neglect all information that is not “visible” for dipaths from a set of initial point to a set of final points. In the applications, one is mainly interested in executions (dipaths) from a specified subset X_{0} ⊂ X ∪ {−∞} of initial points to a specified subset X_{1} ⊂ X ∪ {∞} of final points – or infinitely running executions (infinite dipaths) from a set of initial points. The reason for insisting on sources and targets being subspaces instead of just points (as in [17]) is that inductive calculations may require to cut dipaths and dihomotopies into pieces: “below X_{0}, between X_{0} and X_{1} and above X_{1}”. In many applications, these subsets are achronal, i.e., π⃗_{1}(X_{i})(x, y) = ∅ for x ≠ y, x, y ∈ X_{i}, or even discrete.

The following example – with one point sets X_{0} and X_{1} – shows that the fundamental category often contains information that is not relevant for dipaths starting at X_{0} and ending at X_{1}:

Example 2.4. Let J⃗ ⊂ I⃗ denote an open subinterval, and let Y_{n}^{1}= I⃗^{n} \ J⃗^{n}, a set with minimal point 0 = (0, …, 0) and maximal point 1 = (1, …, 1). It is easy to see that, for n > 2, all dipaths in Y from 0 to 1 are dihomotopic. But the fundamental category π⃗_{1}(Y_{n}) is not trivial. Let I_{−} = {t ∈ I|t ⩽ inf J} and I_{+} = {t ∈ I|t ⩾ sup J}. Then, π_{1}(Y_{n})(x, y) = ∅ if there is an i with x_{i} > y_{i} or if there is an i with x_{i} ∈ I_{−}, y_{i} ∈ I_{+} and all x_{k}, y_{k} ∈ J⃗, k ≠ i. Otherwise, π⃗_{1}(Y_{n})(x, y) has one element unless there are precisely two coordinates 1 ⩽ i < j ⩽ n such that x_{i}, x_{j} ∈ I_{−}, y_{i}, y_{j} ∈ I_{+}^{2} and all other x_{k}, y_{k} ∈ J⃗; in this case, there are two dihomotopy classes of dipaths from x to y.

To get rid of cancellation problems and of superfluous information, we proceed as follows: Two dihomotopy classes β_{1}, β_{2} ∈ π⃗_{1}(X)(x, y) are called equivalent if

γ ∗ β_{1} ∗ α = γ ∗ β_{2} ∗ α ∈ π⃗_{1}(X)(x_{0}, x_{1}) for all α ∈ π⃗_{1}(X)(x_{0}, x)
and all γ ∈ π⃗_{1}(X)(y, x_{1}), x_{i} ∈ X_{i}.

The equivalence class of an element β ∈ π⃗_{1}(X)(x, y) will be denoted by [β], the set of all such equivalence classes by π⃗_{1}(X; [X_{0}, X_{1}])(x, y). Remark that the equivalence

1This space models a shared objects that can be accessed by at most n − 1 out of n competing processes at the same time. 2This corresponds to (x_{i}, x_{j}) ∈ B, (y_{i}, y_{j}) ∈ T in the square with a hole from Fig. 2.

relation is compatible with concatenation. We arrive at a category π⃗_{1}(X; [X_{0}, X_{1}]) whose objects are the elements x ∈ X between X_{0} and X_{1}, i.e., with π⃗_{1}(x)(X_{0}, x) ≠ ∅ ≠ π⃗_{1}(x, X_{1}) and with equivalence classes in π⃗_{1}(X; [X_{0}, X_{1}])(x, y) as morphisms from x to y.

For the equivalence classes of dihomotopy classes, one has then a weak form of cancellation: If

[γ] ∗ [β_{1}] ∗ [α] = [γ] ∗ [β_{2}] ∗ [α] ∈ π⃗_{1}(X)(x_{0}, x_{1})

for all α ∈ π⃗_{1}(X)(x_{0}, x) and γ ∈ π⃗_{1}(X)(y, x_{1}), x_{i} ∈ X_{i}, then [β_{1}] = [β_{2}].

2.3. Aims

It is the aim of this paper to relate dipaths (up to dihomotopy) contributing to the same global information although possibly having different end points, and hereby to define and describe – several versions of – the “components” (cf. Ex. 2.2 and Fig. 2) for general lpo-spaces or d-spaces. As a result, one may compress the fundamental category to one or several component categories that are much smaller – often discrete – but that still contain the essential information.

3. Categories of fractions and components

Since there is nothing special about the fundamental category in the following analysis, this section will be formulated for a general (small) category C.

3.1. The category of fractions Definition 3.1. A subset Σ ⊆ Mor(C) is called a system of morphisms if

1. Σ is closed under composition.

2. 1_{x} ∈ Σ for every x ∈ Ob(C). with 1_{x} denoting the identity on x. The elements of Σ are sometimes called weakly invertible.

Examples for interesting systems of morphisms within a fundamental category will be given in Sect. 4.

For a system Σ of C-morphisms, one may define the category of fractions C[Σ^{−1}] and the localization functor q_{Σ} : C → C[Σ^{−1}] [13, 2] having the following universal property:

• For every s ∈ Σ the morphism q_{Σ}(s) is an isomorphism.

• For any functor F : C → D such that F (s) is an isomorphism for every s ∈ Σ there is a unique functor θ : C[Σ^{−1}] → D with θ ∘ q_{Σ} = F.

It is not too difficult to construct such a category of fractions, cf. [2] for details. Briefly, the objects of C[Σ^{−1}] are just the objects of C. To define the morphisms of C[Σ^{−1}], one introduces an inverse s^{−1} to every morphism s ∈ Σ(x, y) = Σ ∩ Mor(x, y). These inverses are collected in Σ^{−1}(y, x), x, y ∈ Ob(C) and then in Σ^{−1}. Consider the closure of Mor(C) ∪ Σ^{−1} under composition and the smallest equivalence relation containing s^{−1} ∘ s = 1_{x} and s ∘ s^{−1} = 1_{y} for s ∈ Σ(x, y) that is compatible with composition. The equivalence classes constitute the morphisms of C[Σ^{−1}]. A morphism in C[Σ^{−1}] can always be represented [13, 2] in the form

s_{k}^{−1} ∘ f_{k} ∘ ⋯ ∘ s_{1}^{−1} ∘ f_{1}, s_{j} ∈ Σ, f_{j} ∈ Mor, k ∈ N.

In the context of homotopy theory – with topological spaces as objects, continuous maps as morphisms and the weak equivalences as the system of morphisms – categories of fractions are often called the homotopy category of C, cf. e.g. [1, 21].

3.2. The component category

Any morphism of the form s_{1}^{−1} ∘ s_{2} ∘ ⋯ ∘ s_{2k−1}^{−1} ∘ s_{2k}, s_{j} ∈ Σ, k ∈ N is called a Σ-zig-zag morphism. The set ZZ(Σ) of all Σ-zig-zag morphisms forms a system of morphisms contained in the invertibles of the category of fractions, denoted Inv(C[Σ^{−1}]). Equality holds if Σ contains the invertibles Inv(C) of the original category C. The subcategory of C[Σ^{−1}] with all objects, the morphisms of which are given by the zig-zag morphisms ZZ(Σ), forms in fact a groupoid.

Two objects x, y ∈ Ob(C) are called Σ-connected – x ≃_{Σ} y – if there exists a zigzag-morphism from x to y. This definition corresponds to usual path connectedness with respect to paths in Σ only – but regardless of orientation. Σ-connectivity is an equivalence relation; the equivalence classes will be called the Σ-connected components – the path components with respect to Σ-zig-zag paths, i.e., the components of the groupoid above.

Next, consider the smallest equivalence relation on the morphisms of C[Σ^{−1}] generated (under composition) by

α ≃ α ∘ s^{j}, α ≃ t^{j} ∘ α for α ∈ Mor(x, y), s ∈ Σ(x′, x), t ∈ Σ(y, y′), j = ±1. (3.1)

Remark that equivalent morphisms no longer need to have the same source or target. In particular, every morphism in Σ is equivalent to the identities in both its source and its target; hence, all zig-zag morphisms within a component are equivalent to each other.

Dividing out the morphisms in Σ within C, we arrive at a component category: The objects of the component category π_{0}(C; Σ) are by definition the Σ-connected components of C; the morphisms from [x] to [y], x, y ∈ Ob(C), are the equivalence classes of morphisms in ⋃_{x′≃_{Σ}x,y′≃_{Σ}y} Mor_{C[Σ^{−1}]}(x′, y′). The composition of [β] ∘ [α] for α ∈ Mor_{C[Σ^{−1}]}(x, y) and β ∈ Mor_{C[Σ^{−1}]}(y′, z) is given by [β ∘ s ∘ α] with s any zig-zag morphism from y to y′. The equivalence class of that composition is independent of the choices of representatives α and β (by definition) and of the choice of the zig-zag path s by the preceeding remark.

The overall idea is thus as follows: Having fixed a suitable system Σ of “weakly invertible” morphisms, we decompose the study of C into the study of

• the component category encompassing the global effects of irreversibility and • the components with a groupoid structure given by the Σ-zig-zags. The original category C and the component category π_{0}(C; Σ) are related by

a functor π_{0}(Σ) : C→^{q_{Σ}}C[Σ^{−1}] → π_{0}(C; Σ); the last arrow is the quotient functor. Particularly interesting are systems Σ for which π_{0}(Σ) is injective on the morphism sets and bijective on non-empty morphism sets.

3.3. Morphisms between given sources and targets

For a description of components of the quotient category π⃗_{1}(X; [X_{0}, X_{1}]) from Sect. 2.2, we need a modification: Let X_{0}, X_{1} ⊂ Ob(C) denote nonempty sets of objects such that the morphisms in Mor(C) satisfy the following weak cancellation property for β_{i} ∈ Mor(x, y):

γ ∘ β_{1} ∘ α = γ ∘ β_{2} ∘ α for all α ∈ Mor(x_{0}, x), γ ∈ Mor(y, x_{1}), x_{i} ∈ X_{i} ⇒ β_{1} = β_{2}.

(3.2)

Let Mor(X_{0}, X_{1}) = {f ∈ Mor(x_{0}, x_{1}) | x_{0} ∈ X_{0}, x_{1} ∈ X_{1}}. We wish to analyse the structure of Mor(X_{0}, X_{1}) up to an equivalence relation given by a system Σ of morphisms in C. For a given such system, let Σ^{j} := {s ∈ Σ(x, y)| x, y ∈ X_{j}, j = 0, 1}.

Definition 3.2. 1. An elementary equivalence between f ∈ Mor(x_{0}, x_{1}) and g ∈ Mor(x′_{0}, x′_{1} ), x_{0}, x′_{0} ∈ X_{0}, x_{1}, x′_{1} ∈ X_{1} consists of a pair of s ∈ Σ^{0}(x_{0}, x′_{0}), t ∈ Σ^{1}(x_{1}, x′_{1}) such that

\xymatrix{x_{1} \ar[r]^{t} & x′_{1} \\ x_{0} \ar[u]^{f} \ar[r]^{s} & x′_{0} \ar[u]_{g}}

commutes.

2. The symmetric and transitive closure of this relation is called equivalence and compares morphisms from X_{0} to X_{1} under zig-zag morphisms:

\xymatrix{⋯ & x_{1} \ar[l] \ar[r]^{t} & x′_{1} & x′′_{1} \ar[l]_{t′} \ar[r] & ⋯ \\ ⋯ & x_{0} \ar[l] \ar[u]^{f} \ar[r]^{s} & x′_{0} \ar[u]^{f′} & x′′_{0} \ar[l]_{s′} \ar[u]^{f′′} \ar[r] & ⋯}

3. The equivalence classes form the sets Mor_{01} = ⋃_{x_{0}∈X_{0},x_{1}∈X_{1}} Mor(x_{0}, x_{1})_{/∼}.

4. Mor(X_{0}, x) = Mor(X_{0}, {x}) for x ∈ X.

As in the case of the fundamental category of an lpo-space, we want to define systems of morphisms and associated component categories that inherit the essential information in the category C from the perspective of Mor_{01}. In many cases of interest, Σ^{j} will consist only of the identity morphisms on the objects in X_{i} – e.g., if C is the fundamental category of a n lpo-space and the X_{i} are achronal subsets of X, cf. Sect. 2.2. In that case, Mor_{01} = ⋃_{x_{0}∈X_{0},x_{1}∈X_{1}} Mor(x_{0}, x_{1}).

3.4. Induced morphisms. Representations of morphisms Let X_{0}, X_{1} ⊂ Ob(C). By composition, a morphism s ∈ Mor(x, y) induces maps

\begin{aligned}s_{#} : & Mor(X_{0}, x) & → & Mor(X_{0}, y) & s^{#} : & Mor(y, X_{1}) & → & Mor(x, X_{1}) \\ & f & ↦ & s ∘ f & & g & ↦ & g ∘ s. \end{aligned}

Since composition is associative, these induced maps are adjoints under the composition pairings c_{x} at x and c_{y} at y:

\xymatrix{Mor(X_{0}, x) \ar[d]_{s_{#}} & × & Mor(x, X_{1}) \ar[r]^{c_{x}} & Mor_{01}, \\ Mor(X_{0}, y) & × & Mor(y, X_{1}) \ar[u]^{s^{#}} \ar[ur]_{c_{y}}}

or equivalently

[figure: Mor(X_{0}, x); Λ(c_{x}); s_{#}; Mor_{01}^{Mor(x,X_{1})}; (s^{#})^{∗}; Mor(y, X_{1}); Λ(c_{y}); s^{#}; Mor_{01}^{Mor(X_{0},y)}; (s_{#})^{∗}; Mor(X_{0}, y); Λ(c_{y}); Mor_{01}^{Mor(y,X_{1})}; Mor(x, X_{1}); Λ(c_{x}); Mor_{01}^{Mor(X_{0},x)}.]

If the category C satisfies weak cancellation (3.2), the maps Λ(c_{x}) and Λ(c_{y}) are injections.

We associate with a morphism f ∈ Mor(x, y) the set of all its extensions

E(f) = {[g ∘ f ∘ h] | h ∈ Mor(X_{0}, x), g ∈ Mor(y, X_{1})} ⊂ Mor_{01}

from X_{0} to X_{1} up to equivalence. Collecting these, we obtain maps into the power set 2^{Mor_{01}}:

E_{xy} : Mor(x, y) → 2^{Mor_{01}}, E_{xy}(f) = E(f).

Likewise, one obtains extension maps E_{0y} : Mor(X_{0}, y) → Mor_{01}. For f ∈ Mor(x, y) and g ∈ Mor(y, z), one has obviously

E_{xz}(g ∘ f) ⊂ E_{xy}(f) ∩ E_{yz}(g).  (3.3)

Figure 3: Dipaths on the surface of a cube with two holes

Example 3.3. Even in easy geometric examples, equality does not hold in (3.3). In Fig. 3, we consider the surface of a cube with two squares on the front face punched out. The dipaths f and g on the front face can both be extended to the same two (out of three) dihomotopy classes of dipaths from the left front bottom vertex to the right rear top vertex, whereas their concatenation g ∗ f only can be extended to one of them.

4. Applications

4.1. Classes of weakly invertible morphisms

First some trivial cases: If Σ consists of the identity morphisms only, then obviously C[Σ^{−1}] and the component category π_{0}(C; Σ) are equivalent to C. If Σ = Mor, all morphisms in C[Σ^{−1}] are invertible, and the Σ-connected components are the usual path components of C – regarded as a non-oriented graph. The component category π_{0}(C; Σ) has only identity morphisms.

We will now list several more interesting classes Σ_{i} of weakly invertible morphisms. Comments on the respective categories of fractions and component categories, in particular for categories of the form C = π⃗_{1}(X; [X_{0}, X_{1}]) will be given in Sect. 4.2. Let always C denote a small category. Let X_{0} and X_{1} denote non-empty subsets of Ob(C) of source, resp. target objects.

1. Let (X_{0} ↓ C) denote the associated comma category of morphisms under X_{0} - if X_{0} contains just one object, this is just the usual comma category [22]. Let f ∈ Mor(X_{0}, x), g ∈ Mor(X_{0}, y) denote objects in (X_{0} ↓ C). Then

Σ_{1}(f, g) = \{ \begin{matrix}Mor(f, g) & E(f) = E(g) \\ ∅ & else \end{matrix}

with E the extension functor from Sect. 3.4.

2. Now, we turn to the category C itself. For x, y ∈ Ob(C), a morphism s ∈ Mor(x, y) is contained in Σ_{2}(x, y) if and only if s^{#} : Mor(y, X_{1}) → Mor(x, X_{1}) is a bijection.

3. Dually, we let Σ_{3}(x, y) consist of all morphsisms s ∈ Mor(x, y) such that s_{#} : Mor(X_{0}, x) → Mor(X_{0}, y) is a bijection.

4. Σ_{4} = Σ_{2} ∩ Σ_{3} ⊂ Mor.

[figure: X_{1}; x; s; y; !; X_{0}; !]

5. Σ_{5} is a system of morphisms satisfying the extension condition that every diagram

[figure: ·; ∈Σ_{5}; ·; ·; g∈Mor; s∈Σ_{5}; ·; ∈Mor]

can be completed, i.e.,

(Σ_{5} ∘ g) ∩ (Mor ∘ s) ≠ ∅ for s ∈ Σ_{5}, g ∈ Mor.

The diagram

[figure: ·; t_{1}; ·; t_{2}; ·; ·; g; s_{1}; ·; g_{1}; s_{2}; ·; g_{2}]

shows how to fill in the diagram for a composition of morphisms in Σ_{5} by the composition of two “solutions” in Σ_{5}.

6. Likewise, Σ_{6} is a system of morphisms satisfying the extension condition that every diagram

[figure: ·; t∈Σ_{6}; ·; ·; ∈Mor; ∈Σ_{6}; ·; g∈Mor]

can be completed, i.e.,

(f ∘ Σ_{6}) ∩ (t ∘ Mor) ≠ ∅.

Same remarks as for Σ_{5}.

7. Σ_{7} is a system satisfying both extension conditions above.

8. For x, y ∈ Ob(C), let Σ_{8}(x, y) = ∅ if Mor(x, X_{1}) ≠ ∅ = Mor(y, X_{1}) and

Σ_{8}(x, y) = Mor(x, y) else. Dually, one may compare reachability from X_{0}. Particularly interesting are the maximal systems satisfying the requirements for Σ_{i}, 5 ⩽ i ⩽ 7. Maximality makes sense because the system generated by (finitely or infinitely many) such systems under composition satisfies the extension properties, as can be seen from the composition diagrams above, cf. (5).

4.2. Properties and examples

1. For the fundamental category C = π⃗_{1}(X), the comma category (X_{0} ↓ π⃗_{1}(X)) has as objects the dihomotopy classes of dipaths starting in X_{0}. A partial dipath s with g = s ∘ f is contained in Σ_{1} if no “decision” has been made between f and g – all “careers” in π⃗_{1}(X; [X_{0}, X_{1}]) open to f are still open to g. Walking along a zig-zag path does not alter the extension sets of the execution paths en route. “No branching occurs between f and g” is another slogan explaining Σ_{1}.

The component category π_{0}(π⃗_{1}(X; {x_{0}}, {∞}]), Σ_{1}) – with x_{0} an initial point – induces the partially ordered set Ω_{1}(X) defined and investigated by S. Sokołowski, cf. [28, 29].

2. If s ∈ Σ_{2}(x, y), then E(s_{#}(f)) = E(f) for all f ∈ Mor(X_{0}, x). If t ∈ Σ_{3}(x, y), then E(t^{#}(f)) = E(f) for all f ∈ Mor(y, X_{1}).

3. The conditions for Σ_{2}- and Σ_{3}-morphisms are not independent. For a category satisfying weak cancellation (3.2), the (adjunction) diagrams at the end of Sect. 3 show:

s_{#} onto ⇒ (s_{#})^{∗} injective ⇒ s^{#} injective
s^{#} onto ⇒ (s^{#})^{∗} injective ⇒ s_{#} injective.

4. Here is how to interpret the conditions for Σ_{2} if C = π⃗_{1}(X; [X_{0}, X_{1}]):

(a) For every f ∈ π⃗_{1}(X)(x, X_{1}) there exists a “factor” g ∈ π⃗_{1}(X)(y, X_{1}) such that f ∘ h = g ∘ s ∘ h for all h ∈ π⃗_{1}(X)(X_{0}, x).

(b) Factorisation is unique: Two such factors g_{1}, g_{2} ∈ π⃗_{1}(X)(y, X_{1}) satisfying g_{1} ∘ s ∘ h = g_{2} ∘ s ∘ h for all h ∈ π⃗_{1}(X)(X_{0}, x) have the property: g_{1} ∘ h′ = g′_{2} ∘ h′ for all h′ ∈ π⃗_{1}(X)(X_{0}, y).

Analogously for Σ_{3}.

5. The systems Σ_{i}, 1 ⩽ i ⩽ 4 enjoy the “2 out of 3 property”: if two out of s, t, t∘s are contained in Σ_{i}, then so is the last.

6. In a category with weak cancellation (3.2) with respect to X_{0} and X_{1}, one may cancel elements in Σ_{2} on the left: Let f, g ∈ Mor(x′, x), s ∈ Mor(x, y) such that s∘f = s∘g ∈ Mor(x′, y). As a consequence, k ∘s∘f ∘h = k ∘s∘g ∘h for all h ∈ Mor(X_{0}, x′), k ∈ Mor(y, X_{1}). Since s ∈ Σ_{2}, any morphism k′ ∈ Mor(x, X_{1}) can be written in the form k ∘s, whence k′ ∘f ∘h = k′ ∘g ∘h for all h ∈ Mor(X_{0}, x′), k′ ∈ Mor(x, X_{1}). By weak cancellation (3.2), we conclude: f = g. By the same argument, elements in Σ_{3} may be cancelled on the right.

7. For 2-dimensional mutual exclusion models, an algorithm for determining the Σ_{i} components, i = 2, 3, 4 has been described in [17] using results of [26].

8. Every morphism in C[Σ_{5}^{−1}] can be represented in the form s^{−1} ∘ f with s ∈ Σ and f ∈ Mor: It is easy to see (cf. e.g. [2]) that the composition of two morphisms of this type can be rechristened as a morphism of that same type. Similarly, every morphism in C[Σ_{6}^{−1}] can be represented in the form g ∘ t^{−1} with t ∈ Σ and g ∈ Mor.

9. By successive application of the definitions, one obtains: Let x ≃_{Σ_{5}} x′ ∈ Ob(C) and let Mor_{C}(x, y) ≠ ∅. Then there exists y ≃_{Σ_{5}} y′ ∈ Ob(C) with Mor_{C}(x′, y′) ≠ ∅. Likewise, let y ≃_{Σ_{6}} y′ ∈ Ob(C) and let Mor_{C}(x, y) ≠ ∅. Then there exists z ≃_{Σ_{6}} x′ ∈ Ob(C) such that Mor_{C}(x′, y′) ≠ ∅. In particular, for Σ_{7}-components, the existence of morphisms between components can be investigated by examining one arbitrarily chosen object in each component.

10. The conditions for Σ_{i}, i = 5, 6, 7 are stronger than one might think at first glance: Call X_{0}, resp. X_{1} Σ_{i}-closed if

y_{0} ∈ X_{0}, Σ_{6}(x_{0}, y_{0}) ≠ ∅ ⇒ x_{0} ∈ X_{0}, resp. x_{1} ∈ X_{1}, Σ_{5}(x_{1}, y_{1}) ≠ ∅ ⇒ y_{1} ∈ X_{1}.

For a Σ_{5}-closed set X_{1}, the extension property has the consequence that s^{#} : Mor(y, X_{1}) → Mor(x, X_{1}) is onto for a morphism s ∈ Σ_{5}(x, y). Likewise, for X_{0} Σ_{6}-closed, an element s ∈ Σ_{6}(x, y) induces a surjection s_{#} : Mor(X_{0}, x) → Mor(X_{0}, y). Using (3) above, we conclude: s ∈ Σ_{7} ⇒ s^{#} and s_{#} are bijections, and thus Σ_{7} ⊆ Σ_{4}. In particular, we have for f ∈ Mor, s, t ∈ Σ_{7}: E(f) = E(s∘f) = E(f ∘t), cf. (2) above. Moreover, the extension properties show that for g, h ∈ Mor, there exist g′, h′ ∈ Mor such that E(g ∘ f) = E(g′ ∘ s ∘ f), resp. E(f ∘ h) = E(f ∘ t ∘ h′). In other words, not only is there a correspondance of the set of extensions for f and s ∘ f, but there is a similar correspondance for all their “prolongations”.

11. In a category with weak cancellation with respect to sets of initial objects X_{0} and final objects X_{1}, a system Σ_{7} of morphisms admits a left and a right calculus of fractions [2] generalising (8) above: Since the extension properties are the defining property for Σ_{7}, we need only check the following properties [2] for

f, g ∈ Mor(x, y): s ∈ Σ_{7}, s ∘ f = s ∘ g ⇒ ∃s′ ∈ Σ_{7} with f ∘ s′ = g ∘ s′ and t ∈ Σ_{7}, f ∘ t = g ∘ t ⇒ ∃t′ ∈ Σ_{7} with t′ ∘ f = t′ ∘ g.

Since Σ_{7} ⊆ Σ_{4}, we can use (6) to cancel s and t and conclude even more than necessary: f = g.

12. The system Σ_{8} is relevant for the analysis of deadlocks and unsafe regions; the dual version for the analysis of unreachable regions, cf. [10, 11, 26].

Remark 4.1. A straightforward modification of the definitions of weakly invertible systems of morphisms without mentioning subsets of sources and targets (in particular for the fundamental category π⃗_{1}(X) of an lpo-space X) does not give satisfactory results. Recent discussions with E. Haucourt and É. Goubault indicate a solution. This theme will be taken up elsewhere.

Example 4.2. 1. Several examples determining the component categories of simple po-spaces with respect to the systems Σ_{i}, i ⩽ 4, are given in [17].

2. The following example shows that, in general, Σ_{4} does not satisfy the extension conditions for a Σ_{6}-system. Consider again the po-space X that is given as the surface of a cube with two holes on the front face in Fig. 4. The elements x_{0} and x_{2} are contained in the bottom face. It is easy to see, that all of the sets π⃗_{1}(X)(x_{0}, x_{2}), π⃗_{1}(X)(x_{1}, x_{2}), π⃗_{1}(X)(0, x_{i}) and π⃗_{1}(X)(x_{i}, 1) consist of a single element. In particular, the unique element s_{j} ∈ π⃗_{1}(X)(x_{j}, x_{2}) is contained in Σ_{4}(x_{j}, x_{2}), 0 ⩽ j ⩽ 1. On the other hand, the diagram

\xymatrix{x_{0} \ar[r]^{s_{0}} & x_{2} \\  & x_{1} \ar[u]_{s_{1}}}

cannot be completed to a square by Σ_{4}-morphisms: Any element x ⩽ x_{0}, x_{1} is contained in the segment of the front edge and “ahead of” x_{0}. In particular, π⃗_{1}(X)(x, 1) consists of at least two elements, and hence Σ_{4}(x, x_{j}) = ∅, 0 ⩽ j ⩽ 1.

Figure 4: Invertibility on the surface of a cube with two holes

4.3. Relation to history equivalence

In [10], we introduced the homotopy history of a dipath f in X from X_{0} to X_{1} and the associated history equivalence classes. In a categorical framework, those definitions read as follows:

Definition 4.3. Let f ∈ Mor(X_{0}, X_{1}).

1. The history hf of f is defined as

hf = {x ∈ Ob(C)| ∃f_{0} ∈ Mor(X_{0}, x), f_{1} ∈ Mor(x, X_{1}) with f = f_{1} ∘ f_{0}}.

2. Two objects x, y ∈ Ob(C) are history equivalent if and only if x ∈ hf ⇔ y ∈ hf

for all f ∈ Mor(X_{0}, X_{1}). A history equivalence class C ⊂ Ob(C) is thus a primitive element of the Boolean algebra generated by the histories, i.e., an intersection of histories and their complements such that either C ⊆ hf or C ∩ hf = ∅ for all f ∈ Mor(X_{0}, X_{1}) .

Proposition 4.4. Let x, y ∈ Ob(C) and f ∈ Mor(X_{0}, X_{1}).

1. Σ_{2}(x, y) ≠ ∅ implies: x ∈ hf ⇒ y ∈ hf.

2. Σ_{3}(x, y) ≠ ∅ implies: y ∈ hf ⇒ x ∈ hf.

3. Every Σ_{4}-component is contained in a path component of a history equivalence class.

Proof. (1) Let s ∈ Σ_{2}(x, y) and let f = f_{1} ∘ f_{0} with f_{0} ∈ Mor(X_{0}, x), f_{1} ∈ Mor(x, X_{1}). There exists g_{1} ∈ Mor(y, X_{1}) such that f_{1} = g_{1} ∘ s. Hence f = g_{1} ∘ (s ∘ f_{0}), i.e., y ∈ hf.

(2) is proved similarly.

(3) For s ∈ Σ_{4}(x, y), we have thus: x ∈ hf ⇔ y ∈ hf for every f ∈ Mor(X_{0}, X_{1}), and hence: x ∈ C ⇔ y ∈ C for every history equivalence class C. The path s connects x and y.

Prop. 4.4 suggests a method for a start of the construction of the Σ_{4}-components: If you know the dihomotopy classes in π⃗_{1}(X; [X_{0}, X_{1}]), find the history equivalence classes and their path components with respect to zig-zag dipaths in Mor_{C} (those were called the diconnected components in [10]); a further refinement might be necessary. In Ex. 2.2, there are two dihomotopy classes l, r ∈ π⃗_{1}(X)(0, 1) of dipaths from the bottom to the top. It is easy to see, that hl = B∪L∪T and hr = B∪R∪T. Hence, hl ∩ hr = B ∪ T, hl ∩ (X \ hr) = L, hr ∩ (X \ hl) = R, and the remaining intersection of complements is empty. The subspace hl ∩ hr consists of the two Σ_{4}-components B and T.

5. Higher homotopy categories

A first serious attempt to bring higher homotopy into the discussion of po-spaces via methods from algebraic topology was formulated by S. Sokołowski in [28]. In this section, I would like to give a presentation of the definitions and of first results in the categorical framework of this paper.

For a topological space Z (made into a po-space with equality as the partial order) and a local po-space (or d-space) X, let X^{Z} denote the mapping space with the compact-open topology. Maps in X^{Z} come equipped with the pointwise (local) partial order, i.e.,

f ⩽ g ⇔ f(z) ⩽ g(z) for all z ∈ Z  (5.1)

or with an induced d-space structure. A dicylinder, cf. [28] for Z a sphere, is a dimap F : Z × I⃗ → X; equivalently, it may be regarded as a dipath from f = F_{0} to g = F_{1} in X^{Z} with respect to the partial order (5.1).

We can now define a category [Z : X]_{1} which has the maps in X^{Z} as objects. The morphisms between f and g in [Z : X]_{1} are the fixed end dihomotopy classes of dicylinders; i.e., two dicylinders F and G from f to g are dihomotopic, if there is a dihomotopy H : Z × I × I⃗ → X with H(z, t, 0) = f(z), H(z, t, 1) = g(z) and H(z, 0, s) = F (z, s), H(z, 1, s) = G(z, s) for all z ∈ Z, t ∈ I and s ∈ I⃗. Concatenation along g allows us to compose a dicylinder from f to g with a dicylinder from g to h. This concatenation is compatible with dicylinder dihomotopy and thus gives rise to the category [Z : X]_{1}– which is equivalent to the fundamental category of the mapping space X^{Z}. An analogue to the higher fundamental groups is given by the special cases Z = S^{n−1}, n > 1. We call [S^{n−1} : X]_{1} the n-th category of X.

Studying higher homotopy invariants of a po-space X means studying component categories of its nth category. With a source subspace X_{0} ⊂ X and a target subspace X_{1} ⊂ X, one would like to structure the dihomotopy classes of dimaps

f : (S^{n−1} × I⃗; S^{n−1} × {0}, S^{n−1} × {1}) → (X; X_{0}, X_{1}).

Again, the results will depend on the definition of the “weakly invertible” morphisms. Details will be worked out elsewhere. We rephrase and comment some of the findings and examples of S. Sokołowski in [28]:

1. Even if the po-space X does not have any deadlock point x (i.e., π⃗_{1}(X)(x, X_{1}) ≠ ∅ for all x ∈ X, cf. [23, 5, 9]), the mapping spaces very often have lots of them. If X is the po-space from the left part of Fig. 1, a map S^{1} → X whose image intersects both L and R cannot be the bottom of a dicylinder with top

the constant map from S^{1} into the top point.

2. The nth categories can discriminate between po-spaces with equivalent fundamental categories (with given source and target). For an example, let X = I⃗^{3} \ J⃗^{3} denote the po-space from Ex. 2.4, i.e., a 3-dimensional cube with an open subcube removed. All dipaths from 0 to 1 are dihomotopic to each other. Hence, the associated component category π_{0}(π_{1}(X; [0, 1]), Σ_{4}) is trivial. A dicylinder f : S^{1} × (I⃗; 0, 1) → (X; 0, 1) from the bottom to the top induces a map S^{2} ≃ ΣS^{1} → X and is classified (up to dihomotopy) by the integral mapping degree of that latter map. The Σ_{4}-component category of the second category of X contains a bottom and a top element (represented by constant maps) and, for every k ∈ Z, one class inbetween. There are no morphisms between components corresponding to different values k ≠ l. Both the fundamental category and the second category of Y = I⃗^{3} are trivial.

3. The nth categories come with additional structure that ought to be exploited: Evaluation at a base point ∗ ∈ S^{n−1} yields a functor from the nth category of a po-space X to its fundamental category. On the fibre of that functor over a chosen dipath in X, the dicylinders can be concatenated using a suspension coordinate in S^{n−1}.

6. Naturality questions

Let f : X → Y denote a dimap (continuous and preserving local partial orders) between lpo-spaces. It is obvious that f induces a map f_{∗} : π⃗_{1}(X) → π⃗_{1}(Y) between the fundamental categories. If f also preserves base points or base spaces, one may ask whether there is an induced map on the component categories, as well. This is in general not the case:

Example 6.1. Consider the space Y (square with one hole) from Ex. 2.2.1 and the inclusion i : X → Y of the subspace X = B ∪ L ∪ T. Since there is only one dihomotopy class from the bottom point (X_{0} = Y_{0} = {0}) to the top point (X_{1} = Y_{1} = {1}) in X, all morphisms belong to any of the relevant systems of weakly invertible morphisms: For C = π⃗_{1}(X; [0, 1]), we get: Σ_{i} = Mor, 1 ⩽ i ⩽ 8 (for i = 1, we consider the morphisms of the comma category). In particular, X consists of a single Σ_{i}-component. On the other hand, X viewed as a subset of Y decomposes into two or three components – depending on the choice of Σ_{i}, 1 ⩽ i ⩽ 7 – with respect to C = π⃗_{1}(Y; [0, 1]).

There is a simple reason for this failure of naturality: In general, f_{∗} does not map Σ_{i}(X) into Σ_{i}(Y). In particular, there is no reason to expect our systems of morphisms to be preserved unless f_{∗} : π⃗_{1}(X; [X_{0}, X_{1}]) → π⃗_{1}(Y; [Y_{0}, Y_{1}]) is surjective. For another view on this naturality problem, compare S. Sokołowski’s [29].

Is there an intermediate level (between the fundamental category and one of the component categories) on which one can talk about naturality?

6.1. Equivalences of categories with systems of morphisms

In this section, we look at categories C equipped with a system of morphisms Σ ⊂ Mor(C) and an associated equivalence relation (3.1).

Definition 6.2. A functor Φ : (C, Σ_{C}) → (D, Σ_{D}) – with Φ(Σ_{C}) ⊆ Σ_{D} – is called an equivalence if

1. For every g ∈ Mor_{D[Σ_{D}^{−1}]} there exists f ∈ Mor_{C[Σ_{C}^{−1}]} such that Φ(f) ≃_{Σ_{D}} g;

2. for f_{1}, f_{2} ∈ Mor_{C[Σ_{C}^{−1}]}, one has: Φ(f_{1}) ≃_{Σ_{D}} Φ(f_{2}) ⇒ f_{1} ≃_{Σ_{C}} f_{2}.

Pairs (C, Σ_{C}), (D, Σ_{D}) related by an equivalence or a (zig-zag) sequence of equivalences are called equivalent.

Applying the definition to identity morphisms in D, one requires in particular every object in D to be Σ_{D}-connected to an object in the image of Φ. More generally, an equivalence Φ induces an isomorphism Φ_{∗} : π_{0}(C; Σ_{C}) → π_{0}(D; Σ_{D}) between the component categories.

In particular, the quotient functor π_{0}(Σ) : (C, Σ) → (π_{0}(C, Σ), I) – with I consisting only of the identity morphisms on the components – from Sect. 3.2 is an equivalence, by definition. More generally, let Σ′ ⊂ Σ denote a (closed) subsystem of morphisms, and let Σ/Σ′ denote the system of equivalence classes. Then, we get a triangle of quotient functors

\xymatrix{(C, Σ) \ar[d] \ar[dr] \\ (π_{0}(C; Σ′), Σ/Σ′) \ar[r] & (π_{0}(C, Σ), I).}

The diagonal functor is an equivalence. Hence, the vertical functor satisfies (2), and by definition, it satisfies (1), as well. As a result, the horizontal functor has to be an equivalence, as well.

6.2. Induced functors

The following construction allows us to represent a functor Φ : C → D that does not necessarily respect chosen systems Σ_{C} ⊂ Mor_{C} and Σ_{D} ⊂ Mor_{D} by a functor Φ̄ between equivalent categories of a “smaller” size inbetween the original and the component category. Here, two functors are considered equivalent if they can be “conjugated” into each other by a (zig-zag) sequence of equivalences of categories and systems on both sides.

We define the system Σ(Φ) := Σ_{C} ∩ Φ^{−1}(Σ_{D}) to consist of those morphisms, that are weakly invertible in C and whose images are weakly invertible in D. It follows immediately from the definition that Φ(Σ_{Φ}) ⊆ Σ_{D}. We obtain a commutative diagram of functors

\xymatrix{ & (C, Σ_{C}) \ar[d] \ar[ddl] \ar[r]^{Φ} & (D, Σ_{D}) \ar[d] \\  & (π_{0}(C, Σ_{Φ}), Σ_{C}/Σ_{Φ}) \ar[r]^{Φ̄} \ar[dl] & (π_{0}(D, Σ_{D}), I), \\ (π_{0}(C, Σ_{C}), I)}

which “conjugates” Φ into the equivalent functor Φ̄.

Example 6.3. In the case of the functor i_{∗} induced by inclusion i : X = B∪L∪T → Y from Ex. 6.1 on the fundamental categories, Σ_{4}(Y) consists of the dipaths entirely contained in one of the domains B, L, R, resp. T. Hence, Σ_{4}(i_{∗}) consists of the dipaths entirely contained in one of the domains B, L, resp. T. Hence, ī_{∗} is the inclusion of categories

[figure: L; T; L; T; ī_{∗}; B; B; R]

Alternatively, one might consider the lattice of systems contained in a particular system Σ and ask a functor to map “sufficiently” small systems of one lattice into systems of the other. This possibility is currently under investigation.

6.3. An application to the (non)existence of dimaps

An analysis of components and histories (cf. Sect. 4.3) can help to find restrictions to the existence of dimaps between lpo-spaces with specific properties. We use essentially the fact, that a dimap φ : (X; X_{0}, X_{1}) → (Y; Y_{0}, Y_{1}) preserves histories and finite intersections of these: φ(hf) ⊆ h(φ ∘ f) for f a dipath in X from X_{0} to X_{1}.

Example 6.4. Let X and Y denote the two po-spaces from Fig. 5 together with their component categories π_{0}(X; Σ_{4}) and π_{0}(Y; Σ_{4}) with non-commuting and commuting squares (indicated by semicircular arrows). Both spaces X and Y admit exactly four dihomotopy classes of dipaths from the bottom to the top; those on X are given by g_{i} ∗ f_{j}, 0 ⩽ i, j ⩽ 1. Which abstract maps Φ : π⃗_{1}(X)(0, 1) → π⃗_{1}(Y)(0, 1) can be realised by a dimap φ : (X; 0, 1) → (Y; 0, 1)?

The intersection of the (homotopy) histories of all four dihomotopy classes in X from 0 to 1 consists of the union of the components B ∪ M ∪ T. Every dihomotopy class in Y is characterised by the particular “antidiagonal” component R_{i}, 1 ⩽ i ⩽ 4, that it touches. In Y, the union of the six intersections of pairs of histories corresponding to the four dihomotopy classes is not pathwise connected (in the usual sense). Its two path components, denoted C_{0} and C_{1}, consist of the six Σ_{4}- components below, resp. above the antidiagonal.

Figure 5: Two po-spaces and their component categories

If the image of φ_{∗} : π⃗_{1}(X)(0, 1) → π⃗_{1}(Y)(0, 1) contains at least two elements, then either M, and thus its “past” ↓M are mapped into C_{0} – or M and its “future” ↑M are mapped into C_{1}. In the first case, φ_{∗}([g_{i} ∗ f_{0}]) = φ_{∗}([g_{i} ∗ f_{1}]), in the second φ_{∗}([g_{1} ∗f_{i}]) = φ_{∗}([g_{0} ∗f_{i}]), 0 ⩽ i ⩽ 1. We conclude, that the image of φ_{∗} has at most two elements. In particular, there is no surjective dimap φ : (X; 0, 1) → (Y; 0, 1).

7. Concluding remarks

Lisbeth Fajstrup has worked on a translation of the covering concept to categories of lpo-spaces [7]. It turns out, that these “dicoverings”, in general, have fibers with non-constant cardinality. It seems that cardinality is constant along the Σ_{3}-morphisms of the approach of this paper. It is an obvious task to work out an analogue to covering theory, i.e., to relate the combinatorics of (the component categories of) the fundamental categories to the topological investigation.

Certainly, the naturality problems touched upon in Sect. 6 deserve further investigation; a satisfactory framework seems to be crucial for several applications connected to the simulation and bisimulation concepts from concurrency theory. Combined with Grandis’ version [18] of the Seifert-van Kampen theorem, we hope to be able to achieve algorithmic calculations of the (component categories) of fundamental categories, at least for spaces arising from the Higher Dimensional Automata mentioned in the introduction. This is the subject of ongoing work by L. Fajstrup, É. Goubault, E. Haucourt and the author.

References

[1] M. Aubry, Homotopy theory and models, Birkhäuser Verlag, Basel, 1995, Based on lectures held at a DMV seminar in Blaubeuren by H. J. Baues, S. Halperin and J.-M. Lemaire.

[2] T. Borceux, Handbook of Categorial Algebra I: Basic Category Theory, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1994.

[3] R. Brown and P.J. Higgins, Colimit theorems for relative homotopy groups, J. Pure Appl. Algebra 22 (1981), 11–41.

[4] , On the algebra of cubes, J. Pure Appl. Algebra 21 (1981), 233–260.

[5] S.D. Carson and P.F. Reynolds, The geometry of semaphore programs, ACM TOPLAS 9 (1987), no. 1, 25–53.

[6] E.W. Dijkstra, Co-operating sequential processes, Programming Languages (F. Genuys, ed.), Academic Press, New York, 1968, pp. 43–110.

[7] L. Fajstrup, Dicovering spaces, Tech. Report R-01-2021, Department of Mathematical Sciences, Aalborg University, DK-9220 Aalborg Øst, 2001, revised version to appear in Homology Homotopy Appl.

[8] L. Fajstrup, Personal communication, 2002.

[9] L. Fajstrup, É. Goubault, and M. Raussen, Detecting Deadlocks in Concurrent Systems, CONCUR ’98; Concurrency Theory (Nice, France) (D. Sangiorgi and R. de Simone, eds.), Lect. Notes Comp. Science, vol. 1466, Springer-Verlag, September 1998, 9th Int. Conf., Proceedings, pp. 332 – 347.

[10] , Detecting Deadlocks in Concurrent Systems, DTA/LETI/DEIN/SLA 98-61, LETI (CEA - Technologies Avancées), Saclay, France, August 1998, 25 pp.

[11] , Algebraic topology and concurrency, Tech. Report R-99-2008, Department of Mathematical Sciences, Aalborg University, DK-9220 Aalborg Øst, June 1999, conditionally accepted for publication in Theoret. Comput. Sci.

[12] L. Fajstrup and S. Sokolowski, Infinitely running concurrents processes with loops from a geometric viewpoint, Electronic Notes Theor. Comput. Sci. 39 (2000), no. 2, 19 pp., URL: http://www.elsevier.nl/locate/entcs/volume39.html.

[13] P. Gabriel and M. Zisman, Calculus of fractions and homotopy theory, Springer-Verlag, New York, 1967, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 35.

[14] P. Gaucher, Whitehead’s Theorem in Homotopy Theory of Concurrency, Tech. report, IRMA Univ. Strasbourg, 2002.

[15] P. Gaucher and É. Goubault, Topological Deformations of Higher Dimensional Automata, Tech. Report 01760, arXiv:math.AT, 2001, to appear in Homology Homotopy Appl.

[16] É. Goubault, The Geometry of Concurrency, Ph.D. thesis, Ecole Normale Superieure, Paris, 1995.

[17] É. Goubault and M. Raussen, Dihomotopy as a tool in state space analysis, LATIN 2002: Theoretical Informatics (Cancun, Mexico) (S. Rajsbaum, ed.), Lect. Notes Comput. Sci., vol. 2286, Springer-Verlag, April 2002, pp. 16 – 37.

[18] M. Grandis, Directed Homotopy Theory I. The Fundamental Category, Tech. Report 443, Dip. di Matematica dell’ Univ. di Genova, 2001, to appear in Cahiers Top. Géom. Diff. Catég.

[19] , Directed Homotopy Theory II. Homotopy Constructs, Tech. Report 446, Dip. di Matematica dell’ Univ. di Genova, 2001, to appear in Theory Appl. Categ.

[20] J. Gunawardena, Homotopy and concurrency, Bulletin of the EATCS 54 (1994), 184–193.

[21] M. Hovey, Model categories, Mathematical Surveys and Monographs, vol. 63, American Mathematical Society, 1999.

[22] S. Mac Lane, Categories for the working mathematician, Graduate Texts in Mathematics, vol. 5, Springer-Verlag, New York, Heidelberg, Berlin, 1971.

[23] W. Lipski and C.H. Papadimitriou, A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems, Journal of Algorithms 2 (1981), 211–226.

[24] L. Nachbin, Topology and Order, Van Norstrand, 1965.

[25] V. Pratt, Modelling concurrency with geometry, Proc. of the 18th ACM Symposium on Principles of Programming Languages. (1991), 311–322.

[26] M. Raussen, On the classification of dipaths in geometric models for concurrency, Math. Structures Comput. Sci. 10 (2000), no. 4, 427–457.

[27] J. P. Serre, Homologie singulière des espaces fibrés, Ann. of Math. (2) 54 (1951), 425–505.

[28] S. Sokołowski, Classifying holes of arbitrary dimension in partially ordered cubes, Manuscript. Kansas State University, February 2000.

[29] , Categories of dimaps and their dihomotopies in po-spaces and local po-spaces, Preliminary Proceedings of the Workshop on Geometry and Topology in Concurrency Theory GETCO’01 (Aalborg, Denmark) (P.Cousot et al., ed.), vol. NS-01, BRICS Notes Series, no. 7, BRICS, 2001, pp. 77 – 97.

[30] R. van Glabbeek, Bisimulation semantics for higher dimensional automata, Tech. report, Stanford University, 1991.

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/n2a9/v5n2a9.(dvi,ps,pdf)

Martin Raussen raussen@math.auc.dk

Department of Mathematical Sciences, Aalborg University, Fredrik Bajers Vej 7G, DK - 9220 Aalborg Ø