Strictifying and taming directed paths in Higher Dimensional Automata

Directed paths have been used by several authors to describe concurrent executions of a program. Spaces of directed paths in an appropriate state space contain executions with all possible legal schedulings. It is interesting to investigate whether one obtains different topological properties of such a space of executions if one restricts attention to schedulings with ``nice'' properties, eg involving synchronizations. This note shows that this is not the case, ie that one may operate with nice schedulings without inflicting any harm. Several of the results in this note had previously been obtained by Ziemianski. We attempt to make them accessible for a wider audience by giving an easier proof for these findings by an application of quite elementary results from algebraic topology; notably the nerve lemma.

1. Introduction 1.1. Schedules in Higher Dimensional Automata. Higher Dimensional Automata (HDA) were introduced by V. Pratt [13] back in 1991 as a model for concurrent computation. Mathematically, HDA can be described as (labelled) pre-cubical or -sets (cf Definition 2.1). Those are obtained by glueing individual cubes of various dimensions together; directed paths corresponding to a -set respect the natural partial order in each cube of the model. These directed paths correspond to lawful schedules/executions of a concurrent computation; and paths that are homotopic in a directed sense (d-homotopic, cf [3]), will always lead to the same result.
Compared to other well-studied concurrency models like labelled transition systems, event structures, Petri nets etc., it has been shown by R.J. van Glabbeek [7] that Higher Dimensional Automata have the highest expressivity; on the other hand, they are certainly less studied and less often applied so far.
It is not evident which paths one should admit as directed paths: It is obvious that they should progress along each axis in each facet of the HDA; the time flow is not reversible. This is reflected in the notion of a d-path on such a complex. One may ask, moreover, that processes synchronize after a step (either a full step or an idle step) has been taken. This is what tame d-paths have to satisfy, on top. A natural question to ask is whether one can perform the same computations (and obtain the same results) according to whether synchronization is requested all along or not.
It has been shown by K. Ziemiański [17,18] that the synchronization request has no essential significance: The spaces of directed paths and of tame d-paths between two states are always homotopy equivalent. This has two consequences: On the one hand, one may, without global effects, relax the computational model and allow quite general parallel compositions. On the other hand, in the analysis of the schedules on a HDA, one may restrict attention to tame d-paths, ie mandatory synchronization; these are combinatorially far easier to model and to analyze.
1.2. Posets, poset categories, and algebraic topology. Many (sets of) schedules can be formulated in the language of series-parallel pomsets (of events). Tame d-paths "live in" serial compositions of simple Higher Dimensional Automata consisting of a single cube each. General d-paths underpin more complicated schedules, for which parallel composition is involved in the description; cf eg [5] for a detailed description of finite step transition systems accepting pomset languages and [2] for newer developments.
In this paper, we are not interested in the analysis of individual paths/schedules, but in the analysis of the space of all schedules from a start state to an end state, equipped with a natural topology. It turns out that the way subspaces of schedules are glued together is essentially the same, whether synchronization is mandatory or not.
In that line of argument, posets enter the scene in a different manner: We divide the space of all executions (d-paths) into easy-to-analyze subspaces; for tame d-paths, for example, we simply fix a sequence of faces that they are kept in. Refinement is a partial order relation on these face sequences, and we will exploit the combinatorial/topological properties of the poset category of face sequences (called cube chains).
The use of methods from algebraic topology in the analysis of concurrency properties has been advocated in eg [4,9,3] to which we refer the reader for details. In this paper, we will (apart from the proof of Proposition 6.6) only apply one important result from algebraic topology, the so-called nerve lemma [1,10], cf Theorem 6.2. At a first glance, one may say that it allows to apply a divide and conquer strategy: Cut a space into subspaces that are topologically trivial (contractible); also all non-empty intersections of such are assumed contractible. Then all essential information (up to homotopy equivalence) is contained in the way these subspaces are glued together. That glueing can be described by way of a simplicial complex, the nerve of the associated poset category. If the posets associated to different spaces are (naturally) isomorphic, then their nerves and hence the spaces they describe are homotopy equivalent.

Definitions and results
2.1. Definitions. We start with some notation: The unit interval [0, 1] is denoted by I. For two topological spaces X and Y , we let Y X denote the space of all continuous maps from X to Y equipped with s compact open-topology. For Let p 0 : [t 0 , t 1 ] → X and p 1 : [t 1 , t 2 ] → X denote two paths with p 0 (t 1 ) = p 1 (t 1 ). Their concatenation at t 1 is denoted p 0 * t 1 p 1 : [t 0 , t 2 ] → X. (1) [8,9] A d-space consists of a topological space X together with a subspace P (X) ⊂ X I of paths in X that contains the constant paths, is closed under concatenation and under non-decreasing reparametrizations p : I → I. Elements of P (X) are called d-paths.
(2) For x, y ∈ X, we let P (X) y x = {p ∈ P (X)| p(0) = x, p(1) = y} denote the subspace of all d-paths from x to y.
] ⊂ R denote an interval (a < b) and let ϕ : J → I denote any increasing homeomorphism. Then P J (X) := {p • ϕ| p ∈ P (X)} -independent of the choice of ϕ.
In applications to concurrency, the d-spaces under consideration are usually directed -sets, or rather their geometric realizations [13,6,7,3]: (1) A -set X (also called a pre-cubical or semi-cubical set) is a sequence of disjoint sets X n , n ≥ 0; equipped, for n > 0, with face maps d α i : X n → X n−1 , α ∈ {0, 1}, 1 ≤ i ≤ n, satisfying the pre-cubical relations: Elements of X n are called n-cubes, those of X 0 are called vertices.
(2) A -set X is called proper [17] if for every pair x 0 , x 1 ∈ X 0 of vertices there exists at most one cube with bottom vertex x 0 and top vertex x 1 (cf also Section 4.1). (3) A -set is called non-self-linked [3] if every cube c ∈ X n has n k 2 n−k different iterated faces in X k (ie, iterated faces agree if and only they do so because of the pre-cubical relations). (4) The geometric realization of a pre-cubical set X is the space . , x n−1 ). It seems that typical Higher-Dimensional Automata as they occur in concurrency are proper and non-self-linked.
Speaking about a cube c in X (or rather in |X|; we will often suppress || from the notation), we mean actually the image of the quotient map {c} × I dim c ֒→ n≥0 X n × I n ↓ |X|. If X is non-self-linked, then this map is a homeomorphism onto its image in X; if not, then it may identify points on the boundary of I dim c .
What are the directed paths in the geometric realization of a -set?
(1) A path p : J → I on an interval J is called strictly increasing if it is increasing and moreover satisfies: p(t) = p(t ′ ) ⇒ t = t ′ or p(t) = 0 or p(t) = 1.
(2) A path p = (p 1 , . . . , p n ) : J → I n on an interval J is called (strictly) increasing if every component p i is (strictly) increasing.
A directed path p : I → X is called tame if the subdivision in (3) above can be chosen such that p(t i ) is a vertex for every 0 ≤ i ≤ l. A path that is strictly directed and tame is called strictly tame.
Observe that we allow d-paths that include non-trivial directed loops. (1) A Euclidean cubical complex [16] K is a subset of Euclidean space R n that is a union of elementary cubes [k i , k i + e i ] ⊂ R n with k i ∈ Z and e i ∈ {0, 1}. The maximal cubes in the cubical set that it realizes can be described by a pair of bottom and top vertices (k, l) ∈ Z n × Z n with 0 ≤ l i − k i ≤ 1. A Euclidean cubical complex is obviously proper and non-self-linked. Euclidean cubical complexes arise as models for P V -programs (cf eg [3]).
(2) For an example of a non-proper cubical set, consider the cubical set X glued from two squares (2-cubes) along a common boundary (consisting of four oriented edges and of four vertices). Its geometric realization is homeomorphic to a 2-dimensional sphere; but remark that the directed paths on this sphere are quite peculiar. The space of all such directed paths is actually homotopy equivalent to a circle. (3) [19] The -set Z n with exactly one cube in every dimension k ≤ n is obviously selflinked. For a description of d-paths in the geometric realization of this space, cf Example 6.5. (4) [19] The -set Q n has (n − k + 1) k-cubes c k 0 , . . . , c k n−k and face maps d e i c k j = c k−1 j+i+e . It arises from the cube I n by identifying all faces spanned by two vertices with i, resp. k + i coordinates 1 with each other (0 ≤ i ≤ n − k). This -set is proper, but also self-linked.

Different types of schedulings.
D-(irected): paths correspond to executions of a concurrent program -without the possibility to let one or several processes run backwards in time. Strict: d-paths correspond to programs where a particular process only may be idle at a vertex in the program (once a step is fully taken); between steps it needs to move forward in time at "positive speed". Tame: d-paths correspond to programs where processes need to synchronize at every vertex (a number of processes may stay idle inbetween) before progressing; at synchronization events, a process has taken a full step or it has stayed idle. Strict tame: d-paths correspond to programs combining both properties.
Our main result in Theorem 2.6 below states that the spaces of schedulings, regardless of the restrictions above, will have the same topological properties in all four cases.
In the final Section 6.3 we show that one may restrict (up to homotopy equivalence) the space of tame d-paths even further: It is enough to consider Pl d-paths that are piecewise linear with kink points at certain hyperplanes.

2.2.2.
A simple illustrative example. We refer to Figure 2. Let X = ∂I 3 be the -set corresponding to the boundary of a 3-cube. It has twelve edges: four parallel to each of the axes and labelled x, y resp. z and six two-dimensional facets: two parallel to each of the three coordinate planes and labelled xy, xz resp. yz.
The image of every d-path from the bottom vertex 0 to the top vertex 1 is contained in two subsequent square facets; the image of every tame d-path from 0 to 1 is contained in a pair of an edge and a facet. Taking care of intersections, one arrives in both cases at a category with geometric realization in form of a hexagon; homotopy equivalent to the circle S 1 . The space of all d-paths (whether tame or not) in ∂I n is indeed homotopy equivalent to S n−2 .  The -set X = ∂I 3 models the situation where a shared resource can serve two out of three processes but not all of them at the same time. Remark that a sequence like xy|xz (on top of Figure 2) of two subsequent facets can be interpreted as x (y|z), ie x and y|z are executed concurrently. Allowing this may be very convenient and speed up a concurrent execution. For an analysis of the consequences, it is reassuring to realize that the space of schedules between two given states is qualitatively the same regardless whether one allows parallel execution over a series of steps (like in x (y|z)) or only over one step at a time (like in yz).

Main result.
Let X denote a -set with finitely many cubes. For a given pair of vertices x − denote the spaces of directed, strictly directed, tame, and strictly tame dipaths from x − to x + (considered as subspaces of X I with the compact-open topology). Inclusion maps lead to the commutative diagram that also contains (maps into) the nerve of a poset-category C(X) x + x − explained in the sketch of the proof of our result: Theorem 2.6.
(2) For a proper non-self-linked -set X (cf Definition 2.2(2)), all path spaces are homotopy equivalent to the nerve of the category C(X) x + x − . Overview proof. It is shown in Proposition 3.4 by a cube-wise strictification construction that the maps with labels 1 and 2 are homotopy equivalences.
For a -set X and chosen end points x − , x + , we define a poset category C(X) x + x − , cf Section 4.3: An object of that category is a cube chain (cf Definition 4.11(4)) in X connecting x − with x + ; this a sequence of cubes such that the top vertex of each cube in that sequence agrees with the bottom vertex of the subsequent cube. Morphisms in C(X) x + x − correspond then to refinements of cube chains; for details consult Section 4.3.
We prove in Proposition 6.4 for paths in a proper non-self-linked -set X (cf Definition (indicated by the maps 5 and 6 ) and can therefore deduce that also 3 is a homotopy equivalence: Both spaces have a common underlying combinatorial structure! Our proof uses only the classical nerve lemma [1,10], cf Theorem 6.2, and a transparent taming construction (Proposition 5.1) for strict d-paths subordinate to the collar of a cube chain (cf Definition 4.5). The remaining inclusion 4 is a homotopy equivalence as well by the 2-out-of-3 property for homotopy equivalences. In the more involved case of a general -set X, we show in Proposition 6.6 that 3 is a homotopy equivalence using the projection lemma and the homotopy lemma (cf eg [12]) underlying the proof of the nerve lemma.
Remark 2.7. Many of the results in this paper are not new. Ziemianski proved in [18], using elaborate homotopy theory tools, that the space of tame d-paths T (X) x + x − is always homotopy equivalent to the nerve of a more intricate category Ch(X) of cube chains, even for a general -set X. This Reedy category (cf [11]) takes care of identifications on the boundary of cubes in a cube chain. Moreover, he shows by an ingenious global taming construction, that 4 is a homotopy equivalence. Apart from including spaces of strictly increasing paths (necessary in our proof for taming), this note presents a far more elementary argument that, for proper -sets, only uses the nerve lemma.  3)) with the following properties: Proof. One way to construct such a directed map is as the restriction of the flow of the differential equation y ′ = g(y) corresponding to a smooth function g : I → R with g(0) = g(1) = 0 and g(t) > 0, 0 < t < 1, e.g. g(t) = t − t 2 . For this choice, the function given by F (t, x) = xe t 1−x+xe t has the required properties.
The homotopy F on the interval I from Lemma 3.1 can be used to define a diagonal continuous directed homotopy F : I × I n → I n on the cube I n by F(t; x 1 , . . . , x n ) = (F (t, x 1 ), . . . , F (t, x n )). Remark that F respects all (sub)-faces of I n because of Lemma 3.1 (1). Applying this construction cube-wise (the same for every k-cube!), we define for every (geometric realization of a) semi-cubical set X, a continuous directed map F : I × X → X that lets all cubes -and in particular all vertices -invariant.

3.2.
Strictification is a homotopy equivalence. Using such a directed map F, we define a map S : Proof.
Proof. The metric d 1 corresponding to the l 1 -norm on individual cubes extends to a metric d 1 on X (the distance between two points being the infimum over the sum of distances on connecting chains) that induces the topology on X. The compact open topology on a function space with target X corresponds to the uniform convergence topology with respect to that metric d 1 .
If X is a finite complex, then I × X is compact, and hence the restriction F : I × X → X is uniformly continuous with respect to the metrics induced by d 1 .
Proposition 3.4. Let X denote a finite pre-cubical set with vertices x − and x + . Then the inclusions ι : Proof. The homotopy S : connects the identity map (for s = 0) with the map ι • S (for s = 1). Its restriction to S(X) x + x − connects the identity map on that space with S • ι.
The restriction of S to a map from (1) Every d-path p ∈ P (X) x + x − can thus be arbitrarily well approximated by a strict d-path of the form S(s, p), s > 0. This shows that Arbitrarily close to any strict d-path there is a d-path that "pauses" on a tiny interval.

Cube chains and collars
4.1. The collar of a face in a cube. We propose a user-friendly notation for repeated face maps in a cube -and then in a -set: Every partition [1 : n] = I 0 ⊔ I * ⊔ I 1 defines a face For a -set X, an n-cell c in X and a partition I 0 ⊔ I * ⊔ I 1 , the combinatorics of the quotient map q : . Remark that (for a self-linked -set), different partitions (of the same cardinality) can give rise to the same face.
If d and c are cubes in X, the collar of d in c is defined as (2) For a cube chain with vertices, we require only dim c i ≥ 0, ie we allow vertices within such a cube chain.
(1) To every cube chain with vertices one may associate a cube chain without vertices by simply leaving out every vertex.
(2) A cube chain in a -set X defines a vertex sequence (x − = x 0 , x 1 , . . . , x n , x n+1 = x + ) but, if X is not proper, not the other way round: More than one cube may share the same bottom and top vertex.
Let us for a moment focus on a single n-cube c in a -set X (with quotient map q : I n → c) and on certain d-paths in its collar C(c, X) connecting a point in st(c 0 ) with a point in st(c 1 ):  (1) The subspace T c (X) ⊂ T (X) of d-paths subordinate to c consists of d-paths with presentation p = [c 1 ; The subspace P C c (X) ⊂ P (X) of d-paths subordinate to the collar C(c) of c consists of d-paths p = p 1 * t 1 · · · * t n−1 p n with p j subordinate to the collar of c j in X.    (1), or if p is the concatenation of two paths subordinate to the collar of (e) at some point on the edge e. In either case, q(0.5, 0.5) is not contained in the image of p.  (1) Every cube chain c -and hence also its collar C(c) -contains a tame strict d-path.
(2) For every strict d-path p ∈ S(X) x + x − , there exists a cube chain c(p) such that p ∈ S C c(p) (X) x + x − . In the following proof, we will make use of coordinate hyperplanes in a cube chain. In a cube I n , consider middle hyperplanes given by the equations x i = 0.5, 1 ≤ i ≤ n. The elementary but crucial observation is that a strict d-path intersects any coordinate hyperplane in at most one point. Likewise, one defines coordinate middle hyperplanes (potentially with identifications on the boundary, one boundary middle hyperplane being identified with another such) in each cube in a -set X. Proof.
(1) The diagonal path δ n in ST (I n ) 1 0 connects bottom and top vertex of the n-cube diagonally with constant speed. For an n-cell c in X, composition with the quotient map I n ↓ c defines a strict tame path δ(c) in c from its bottom vertex to its top vertex. The concatenation δ(c) := δ(c 0 ) * · · · * δ(c n ) defines a strict tame path in the cube chain c connecting bottom and top vertex.
(2) For every strict d-path p : J = [j − , j + ] → I n in a single cube I n defined on some interval J ⊆ I, there is a finite set S ⊂ J (possibly empty) consisting of s j ∈ J at which p intersects one or several of the middle hyperplanes x i = 0.5, 1 ≤ i ≤ n. Define I j 0 , I j * , I j 1 as the set of indices i for which p i (s j ) is less than, equal, resp. greater than 0.5. Since p is strict, we have that I j+1 ] I n of the cube chain is minimal containing p(j + ). Now let p : I → X denote a strict d-path in a -set X from x − to x + with presentation p = [c 1 ; p 1 ] * t 1 [c 2 , p 2 ] * t 2 · · · * t l−1 [c l , p l ]. Then the construction above can be performed for each individual cube c i leading to a sequence c(p) of cubes the collar of which contains p(I). One has to check that two subsequent cubes "match": If p i (t i ) = p i+1 (t i ) is not contained in any middle hyperplane, then it is contained in the star of a vertex which is the top vertex in the cube chain corresponding to p i and the bottom vertex in that corresponding to p i+1 . If p i (t i ) = p i+1 (t i ) is contained in a middle hyperplane, then the last cube in the cube chain corresponding to [c i , p i ] agrees with the first one in the cube chain corresponding to [c i+1 , p i+1 ], ie the minimal cube in the boundary of c i and of c i+1 containing p i (t i ) -according to (b) above.
In a final step, one may erase cubes consisting of a single vertex; cf Remark 4.3(1). Figure 6. D-paths in two subsequent cubes in blue; the corresponding cube chains in orange, their collars in yellow. In the first two cases the two cube chains associated to each individual square consist of a single cube with common top, resp. bottom vertex; in the last case, the two cube chains share a common edge cube.  refinements. (4) Refinement between cube chains in X from a vertex x − to a vertex x + defines a partial order relation among cube chains that gives rise to a thin (poset) category C(X) x + x − with cube chains as objects and refinements as morphisms.
Remark that, for a general -set X, the category Ch(X) in Ziemiański's [18] differs from this poset category. Ziemianski's cube chains are concatenations of cubical maps from a standard cube into a cube in X; moreover cubical symmetries of the standard cube that induce identities in the -set are an additional part of the structure. ( For every strict d-path p ∈ S(X), the chain c(p) (Proposition 4.9(2)) is finest among the cube chains c with p ∈ S C c (X) x − intersect iff c and c ′ have a common refinement. Likewise for spaces of strict tame paths.
If X is proper and non-self-linked (cf Definition 2.2(2-3)), then two cube chains either do not have a common refinement or they have a coarsest one (for which equality holds in (5)). (7) Similar results hold for spaces of strict and tame d-paths. Proof.
(2) The diagonal path in ST c (X) from the proof of Proposition 4.9(1) is not contained in S C c ′ (X) x + x − . (3) Every elementary refinement (cf above) of the cube chain c(p) described above results in a collar that does not intersect at least one of the hyperplanes x j = 0.5 with j ∈ I * within a cube c i . In particular, it cannot contain p(I) which has a non-empty intersection with this hyperplane. (4) ⇐ follows from (1) and Proposition 4.9.
⇒: By (3) above, the cube chain c(p) for a path p in the intersection refines both c and c ′ . (5) The first part follows from (1) above.
Refinement of cube sequences is reflected in inclusion of path spaces (Proposition 4.12(1)). As a result of Proposition 4.9 and 4.12, we conclude: Corollary 4.14. Let X denote a -set with vertices x − , x + ∈ X 0 . Then The colimit identifies path spaces in finer cube chains with subspaces of path spaces in coarser ones; the colimit is therefore just a union of topological spaces.

Comparing paths in a cube chain and in its collar
Let c = (c 1 , . . . , c n ) denote a cube chain in a -set X between vertices x − and x + . The purpose of this section is to establish Proof.
(1) will be proved through a cubewise taming construction -first for individual d-paths and then for spaces of such. The proof of (2) follows the same pattern; you need to check that the d-paths and d-homotopies in the construction below stay tame.
To prove (1), we consider in a first step only strict d-paths subordinate to the collar of a cube chain d = (d 1 , . . . , d k ) within the standard cube I n ; d j is the face Consider the sequence of piecewise linear hypersurfaces H j ⊂ I n , 1 ≤ j < k, given by the equations m j (x) = 1, x ∈ I n , with m j (x 1 , . . . , x n ) := min i∈I j * x i + max i∈I j+1 * x i . The intersection of H j with the collar of the cube d l in I n is empty unless l = j or l = j + 1: In these collars, the coordinates x i satisfy either all x i < 0.5 or x i > 0.5 for i ∈ I j * ∪ I j+1 * . H j intersects the collars of d j and d j+1 within the collar of the vertex v j . For a strict d-path, p ∈ S C d (I n ), consider the functions given by the compositions m j • p : I → R, 1 ≤ j ≤ k; they are strictly increasing. When p enters st(v j ) at t = t − , we have min i∈I j * p i (t − ) = 0.5, whereas max i∈I j+1 * p i (t − ) < 0.5; their sum being less than 1; when p exits st(v j ) at t = t + , we have max i∈I j+1 * p i (t + ) = 0.5 and min i∈I j * p i (t + ) > 0.5; their sum being greater than 1. We conclude that there exists a unique ascending sequence t 1 < t 2 < · · · < t k−1 such that min i∈I j * and p i (t j ) > 0.5 for i ∈ I j 1 . We define a tame d-path t(p) = q as the concatenation q 1 * t 1 q 2 * t 2 · · · * t k−1 q k of strict d-paths q j : [t j−1 , t j ] → d j (from v j−1 to v j ): the components q j i , 1 ≤ i ≤ n, of q j are given by Furthermore, we define a linear d-homotopy H = H s of strict d-paths H s ∈ S C d (I n ) connecting p and q as H(t, s) = (1 − s)p(t) + sq(t).

Remark 5.3.
(1) Formula (5.2) has the following interpretation: On the interval [t j , t j+1 ], the components of p in I j 0 resp. in I j 1 are compressed to 0, resp. 1 (the respective processes in an HDA are idle), whereas its components in I j * are stretched to fill the entire interval (the respective processes take a full step). Remark that q(t j ) is a vertex for every 0 ≤ j ≤ k.
(2) If the cube chain d consists of a single cube only (a face, that may be just a vertex, but also the entire cube), then t(p) = q is given by formula (5.2) for q on the entire domain -no concatenation involved. (3) For a strict d-path p that is already contained in the cube chain c itself, p(t) solves the equation min i∈I j * x i + max i∈I j+1 * x i = 1 exactly at t j with p(t j ) = v j . Hence t(p) = p and H(t, s) = p(t) for s ∈ I.
Lemma 5.4. For every cube chain d in I n , the times t j = t j (p), 1 ≤ j < k, define continuous Proof. Given a d-path p ∈ S C d (I n ) and ε > 0 consider the open set of all strict d-paths q satisfying m j (q(t j (p) − ε)) < 1 and m j (q(t j (p) + ε)) > 1. Obviously, it contains the path p. For a strict d-path satisfying these two inequalities, the solution t =: t j (q) of m j (q(t)) = 1 is contained in the interval (t j (p) − ε, t j (p) + ε).
Proof of Proposition 5.1 continued. In the sequel, we assume given a strict d-path p ∈ S C c (X) x + x − . Let us fix a presentation (cf Definition 2.3(3)) and perform the taming construction above cubewise. It is not difficult to check that, since the cube chain and its collar are unchanged, the resulting tamed path and d-homotopy does not depend on the chosen presentation. Moreover, the tamed d-paths in subsequent cubes (and the d-homotopies) "fit" at top, resp. bottom vertices of the cube chain.
Finally, Lemma 5.4 and formula (5.2) show that the construction yields a continuous taming map T : x − ) I such that H 0 = id and H 1 is given by T -composed with an inclusion map. Moreover, Remark 5.3(3) shows that H leaves S c (X) elementwise fixed. 6. Taming is a homotopy equivalence 6.1. Proper and non-self-linked -sets. In this section, we deal with a proper non-selflinked -set X (cf Definition 2.2(2)). For a such, the taming result ( 3 in Theorem 2.6) is a consequence of the nerve lemma. This is essentially due to Proposition 6.1. Let X denote a proper non-self-linked -set and let c denote a cube chain in X from x − to x + . Furthermore, let also c 1 , . . . c k denote cube chains in X from x − to x + .
(1) The spaces S c (X) x + x − and P c (X) x + x − of (strict) d-paths subordinate to c are contractible.
x − are contractible if the cube chains c i possess a common refinement and empty otherwise. Proof.
(1) For P c (X) x + x − , this has been observed in [17,Proposition 6.2(1)]. In brief, the space of d-paths in a single cube from the bottom to the top vertex is contractible (to the unit speed diagonal path joining them, say) by a linear d-homotopy. For paths in a general cube chain, perform first a reparametrization homotopy joining every d-path with its naturalization [15], ie, a unit speed path with respect to the l 1 -norm along the same trajectory. The space of natural d-paths can then be contracted cube-wise.
For S c (X) x + x − , one can either go through the same steps for strict d-paths or one can refer to Proposition 3.4 (or rather its proof) in the current paper.
(2) For S C c (X) x + x − , this follows from (1) and Proposition 5.1. For P C c (X) x + x − , apply then Proposition 3.4 (or rather its proof).
(3) follows from (2) and Proposition 4.12 (6). Theorem 6.2 (Nerve lemma [1,10]). Let Z denote a paracompact topological space and let U denote a good covering Z = U i of Z by open sets U i ⊂ X, ie all non-empty intersections i∈I U i are contractible. Then X is homotopy equivalent to the nerve of the poset of these non-empty intersections ordered by inclusion.
This nerve is a simplicial complex with vertices corresponding to the U i and (k − 1)dimensional simplices corresponding to non-empty intersections i∈I U i . Corollary 6.3.
(1) The space S(X) x + x − of strict d-paths is homotopy equivalent to the nerve of a covering U (X) x + x − ; likewise, the space ST (X) x + x − of strict tame d-paths is homotopy equivalent to the nerve of a covering V(X) x + x − . (2) The two spaces are homotopy equivalent to each other. (2)) by open (Proposition 4.8 (2)) and contractible (Proposition 6.1) sets; intersections of sets in the covering are empty or contractible by Proposition 6.1 (3). Hence the covering x − are metrizable and thus paracompact, cf [15]. Apply the nerve lemma, Theorem 6.2 to show (1) above.
The two coverings correspond to each other through inclusion maps over the same poset and giving rise to the same nerve: By Proposition 4.12(4), its objects can be enumerated by all sets {c i } of cube chains in X from x − to x + that possess a common refinement (the partial order is generated by refinement and superset).
The remaining paragraphs in this section are not important for the main result, but they lead to a far simpler poset with a smaller nerve, better suited for calculations: The poset category corresponding to the covering U (X) x + x − is very redundant: By Proposition 4.12(4), its objects can be enumerated by all sets {c i } of cube chains in X from x − to x + that possess a common refinement (the partial order is generated by refinement and superset).
x − denote the poset correponding to the covering U (X) x + x − described in the proof of Corollary 6.3 Consider the poset map P U (X) x + x − → C(X) x + x − that associates to a set {c i } of cube chains the coarsest common refinement of all the c i . The fiber (ie comma category) over any c ∈ C(X) x + x − has the set {c} as an initial element, and is thus contractible. Apply Quillen's Theorem A! [14] 6.2. General -sets. I am indebted to K. Ziemiański for pointing out to me that Proposition 6.1 is no longer true for non-proper -sets. Example 6.5. Let Z n denote the unique -set with exactly one cube c k , 0 ≤ k ≤ n, from Example 2.4 (3). For n = 2, consider the cube chain c consisting of the single cube c 2 from c 0 to c 0 . Then S c (X) c 0 c 0 is homotopy equivalent to a circle S 1 -and hence not contractible! In fact, it deformation contracts to the subspace of piecewise linear d-paths in c 2 connecting c 0 with itself through a point on the anti-diagonal (connecting c 0 with itself).
For a general -set X, the proof of Theorem 2.6(1) requires a little more machinery from algebraic topology: Instead of the nerve lemma itself, we apply two more general results in homotopy theory that are used in proving it: the projection lemma comparing colimits with homotopy colimits and the homotopy lemma comparing homotopy colimits of spaces that can be glued together from pieces that are mutually homotopy equivalent. For a quite elementary presentation, cf eg [12]. Using these two results, we can prove that taming is a homotopy equivalence also for general -sets: Proposition 6.6. Let X denote a -set with selected vertices x − , x + ∈ X 0 . Then the inclusion map ι : x − is a homotopy equivalence. Proof. The proof proceeds by a series of homotopy equivalences (denoted ∼ =) : In both cases, the first homotopy equivalence is due to the projection lemma, the second to the homotopy lemma and Propostion 5.1. Paths subordinate to a cube chain c are automatically tame, hence S c (X) x + x − = ST c (X) x + x − . Remark 6.7. By far more sophisticated homotopy theoretical methods, Ziemiański proved in [18] that T (X) x + x − is homotopy equivalent to the nerve of a Reedy category Ch(X) instead of our poset category C(X) x + x − , also for general -sets. He uses a filtration of T (X) x + x − by differently defined contractible subsets using tame presentations. But these subspaces do not define an open covering, and therefore it is not possible to obtain the result by invoking the nerve lemma! Furthermore, Ziemiański shows that T (X) x + x − ֒→ P (X) x + x − is a deformation retract by a global taming construction that is far more tricky than our local one (which is supposed subordinate to the collar of a cube chain).
6.3. PL d-paths and spaces of sequences. In this final section, we restrict attention to proper non-self linked -sets (cf Definition 2.2(2-3)). At least for these, it is possible to find an even smaller model describing the homotopy type of the space of all d-paths between two vertices: To this end, consider the intersections H k of an n-cube I n (and hence of an n-cube in a -set X) with the hyperplanes given by the equations x 1 + · · · + x n = k, k ∈ N, 0 < k < n; different from the hyperplanes previously considered. Every hyperplane section H k is an (n − 1)-dimensional polyhedron with the vertices with k entries 1 and n − k entries 0 as extremal points. Requesting certain variables to take the value 0 or 1 yields the restriction of these hyperplane sections to faces; on which they again are hyperplane sections.
Observe that two elements x k ∈ H k and x k+1 ∈ H k+1 such that x k ≤ x k+1 (ie there exists a d-path from x k to x k+1 ) have l 1 -distance (aka. Manhattan distance) d 1 (x k , x k+1 ) = 1.
The hyperplane sections H k ⊂ I n are achronal: Each d-path p in I n intersects a hyperplane section H k in at most one point p k ∈ H k ; if defined, d 1 (p k , p k+1 ) = 1. The union of all hyperplane sections H k corresponding to all cells in the geometric realization of a -set X form a subspace H(X) ⊂ X. Any d-path between two elements of H(X) has integral l 1length (which is thus invariant under directed homotopy). The shortest length is called their l 1 -distance d 1 ; compare [15] for this concept in greater generality.
A d-path p : A reparametrization linearly adjusting the domain to length one defines an inclusion map ι N : N (X) x + x − ֒→ P (X) x + x − . Analogous to reparametrization by unit speed for curves, one defines a naturalization map in the opposite direction and proves it to be a homotopy inverse: Proposition 6.8. [15,18] For a -set X with selected vertices x − , x + ∈ X 0 , the inclusion map ι N : x − is a homotopy equivalence. The natural tame d-paths form a subspace with inclusion ι N T : N T (X) x + x − ֒→ N (X) x + x − ; naturalization preserves the trace of d-paths and hence tame d-paths and tame d-homotopies stay tame under naturalization: Corollary 6.9. For a -set X with selected vertices x − , x + ∈ X 0 , the inclusion map ι N T : N T (X) x + x − ֒→ T (X) x + x − is a homotopy equivalence. Remark 6.10. Let p : J → X on an interval with min J = 0 denote a natural d-path in X.
(2) If p is tame, then p(i) and p(i + 1), i an integer, are contained in a common cube. A minimal such cube is uniquely determined since X is proper. Moreover, since X is non-self-linked, there is a unique unit speed line segment d-path (of length 1) in this (and any other) cube containing them.
A path p ∈ N T (X) x + x − with p(0) = x − is called P L (piecewise linear) if, for every integer i in its domain, the path between p(i) and p(i + 1) is given by the unit speed line segment (of l 1 -length 1) in the minimal cube that contains them both. These P L paths between x − and x + form the subspace P L(X) x + x − ⊂ N T (X) x + x − . Proposition 6.11. Inclusion ι P L : P L(X) x + x − ֒→ N T (X) x + x − ֒→ T (X) x + x − ֒→ P (X) x + x − is a homotopy equivalence.
Proof. In view of Theorem 2.6 and Corollary 6.9, it remains only to show that the first inclusion is a homotopy equivalence. In fact, P L(X) x + x − is a deformation retract in N T (X) x + x − : To a natural tame d-path p : J → X associate the PL d-path L(p) obtained by linearly connecting p(i) with p(i + 1) for i, i + 1 ∈ Z ∩ J in the unique minimal cube containing both, cf Remark 6.10. Observe that p = L(p) if p is P L. The (natural) convex combination homotopy joining p ∈ N T (X) x + x − with L(p) shows that the linearization map L thus defined is a homotopy inverse to the first inclusion map. It restricts to the constant homotopy on P L(X) x + x − . The only data needed to describe P L d-paths are the kink points p(i) in the cubes they traverse: The space Seq(X) x + x − is defined as the space of all finite sequences (x 0 = x − , . . . , x n = x + ) ∈ n≥0 H(X) n+1 with x i , x i+1 in a common cube such that x i ≤ x i+1 and d 1 (x i , x i+1 ) = 1.
Example 6.12. Consider the boundary of X = ∂I 3 from Section 2.2.2. The hyperplane sections (diagonal lines) in the six boundary squares form two triangles, cf Figure 9. The associated pairs (= sequences) of kink points between the bottom and the top vertex form a hexagon, homotopy equivalent to a circle S 1 : With this definition, we obtain Proposition 6.13. Let X be a proper non-self-linked -set with selected vertices x − , x + ∈ X 0 . Then P (X) x + x − and Seq(X) x + x − are homotopy equivalent. Proof. We may replace P (X) x + x − by P L(X) x + x − by Proposition 6.11. The forgetful map that associates to a path p ∈ P L(X) x + x − the sequence (p(i)) ∈ Seq(X) x + x − -with i running through the integers in its domain -is a homeomorphism. Its inverse is the map that associates to a sequence in Seq(X) x + x − the P L-path that connects any two subsequent elements in the sequence by the unit speed line segment in the unique minimal cube containing them both. Remark 6.14. Extending the results of this section to a general -set X seems to be more intricate. The main reason is that, in some cases, two elements in successive hyperplane sections can be joined by more than one unit speed line segment paths -through different cubes if X is not proper and/or through the same cube if X is self-linked. For example, two vertices in subsequent hyperplane sections may be connected by various edges, after identification of vertices.
It seems to be necessary to replace the cube chains from this paper by the cube chains Ch(X) in Ziemiański's paper [18]; those are generated by cubical maps from a wedge of cubes into X. Hyperplane sections in X are then replaced by hyperplane sections in a wedge of cubes. In such a wedge of cubes (which is obviously both proper and non-self-linked), there is a well-defined unit speed line segment between points on consecutive hyperplane sections.