Homology, Homotopy and Applications, vol.5(2), 2003, pp.211–231

ORDINARY AND DIRECTED COMBINATORIAL HOMOTOPY, APPLIED TO IMAGE ANALYSIS AND CONCURRENCY

MARCO GRANDIS

(communicated by Gunnar Carlsson)

Abstract

Combinatorial homotopical tools developed in previous works, and consisting essentially of intrinsic homotopy theories for simplicial complexes and directed simplicial complexes, can be applied to explore mathematical models representing images, or directed images, or concurrent processes.

An image, represented by a metric space X, can be explored at a variable resolution ϵ > 0, by equipping it with a structure t_{ϵ}X of simplicial complex depending on ϵ; this complex can be further analysed by homotopy groups π_{n}^{ϵ}(X) = π_{n}(t_{ϵ}X) and homology groups H_{n}^{ϵ}(X) = H_{n}(t_{ϵ}X). Loosely speaking, these objects detect singularities which can be captured by an ndimensional grid, with edges bound by ϵ; this works equally well for continuous or discrete regions of euclidean spaces.

Similarly, a directed image, represented by an “asymmetric metric space”, produces a family of directed simplicial complexes s_{ϵ}X and can be explored by the fundamental n-category ↑Π_{n}^{ϵ}(X) of the latter. The same directed tools can be applied to combinatorial models of concurrent automata, like Chu-spaces.

Introduction

We discuss here applications of some tools of combinatorial algebraic topology, developed by the author in three recent works:

- an intrinsic homotopy theory for simplicial complexes, in [10, 12];

- fundamental n-categories for simplicial sets and directed simplicial complexes, in [12];

- a study of the (classical) homology theory of simplicial complexes, in [11]. To give a first idea of these applications, consider the subset X ⊂ R^{2} of fig. (a),

representing a planar image we want to analyse, for instance a map of a region of land (or sea).

Received September 4, 2001, revised May 13, 2002; published on April 22, 2003. 2000 Mathematics Subject Classification: 68U10, 68Q85, 54E35, 54E15, 55U10, 05C38, 55Q05, 55N99, 54G99. Key words and phrases: Image processing, concurrent processes, metric, quasi-pseudo-metric, simplicial complex, graph theory, homotopy groups, homology groups, digital topology, mathematical morphology. \begin{matrix}c \\ ◯ \end{matrix} 2003, Marco Grandis. Permission to copy for private use granted.

Viewing X as a topological space, we keep some relevant information, e.g. the fact that X is path-connected, with two “holes”; this can be detected by the usual tools of algebraic topology, homotopy or homology groups. However, we miss all metric information and are not able to distinguish a lake from a puddle (or an island from a pebble). Further, if this “continuous” subspace X is replaced by its discrete trace X′ = X ∩ (ρZ × ρZ) of fig. (b), scanned at resolution ρ = 1/2, we miss any topological information: X′ is a discrete space.

It is more useful to view X and X′ as metric spaces (we shall generally use the ℓ_{∞}- metric of the plane, d(x, y) = max(|x_{1} − y_{1}|, |x_{2} − y_{2}|, essentially because this is the metric of the categorical product R×R, cf. Section 4), and explore them at a variable resolution ϵ (0 ⩽ ϵ ⩽ ∞). This will mean to associate to a metric space X a simplicial complex t_{ϵ}X at resolution ϵ, whose distinguished parts are the finite subsets ξ ⊂ X with diam(ξ) ⩽ ϵ, and study this complex by combinatorial homotopical or homological functors; such functors are based on paths formed of finite sequences (a_{0}, …, a_{p}) of points of X, where each pair {a_{i−1}, a_{i}} is a distinguished subset: d(a_{i−1}, a_{i}) ⩽ ϵ; deformations of such paths derive from similar 2-dimensional nets (which depend on distinguished quadruplets).

Thus, the fundamental group π_{1}^{ϵ}(X) = π_{1}(t_{ϵ}X) of the metric space X, at resolution ϵ, allows us to distinguish, in fig. (a): two basins at fine resolution (0 < ϵ < 1); then, one basin for 1 ⩽ ϵ < 3; and finally no relevant basin at coarse resolution (ϵ ⩾ 3). The finite model X′ gives the same results, as soon as ϵ ⩾ ρ; while, if ϵ < ρ, i.e. if the resolution of the analysis is finer than the scanner’s, we have a totally disconnected object. Thus, a “very fine” resolution can be of scarce interest and too affected by the plotting procedure or by errors; generally, the whole analysis is of interest, and can be expressed - as above - by some critical values (detecting metric characters of the image) and the value of our homotopical invariant within the intervals they produce.

A more detailed discussion of such applications will be given in Section 4, after a brief introduction of simplicial complexes (Section 1), their directed analogue (Section 2), and the fundamental groupoid or category of such structures (Section 3). We also consider, in Sections 5-7, “directed images”, explored by the fundamental category ↑Π_{1}^{ϵ}(X) of a generalised asymmetric metric space, in the sense of Lawvere [18]. The analysis is similar to that given by Fajstrup - Goubault - Raussen [5] for topological spaces equipped with a local partial order, as continuous models of concurrent processes; in Section 8 we show how our fundamental category can be used to explore directed homotopical properties of combinatorial models of concurrency, like Chu-spaces (cf. Pratt [21] and references therein). Higher dimensional aspects of (non-directed) images can be more easily studied by higher homology groups H_{n}^{ϵ}(X) = H_{n}(t_{ϵ}X), as sketched here in Section 9 (and dealt with in [11]).

Finally, Sections 10 and 11 outline the main devices for computing our invariants: telescopic homotopies, a van Kampen theorem for the combinatorial fundamental groupoid, the Mayer-Vietoris sequence for combinatorial homology groups; such devices are then applied to compute some cases previously discussed (10 (c), (d)). We end by recalling that, for the particular metric space X of fig. (a), π_{1}^{ϵ}(X) always coincides with the topological π_{1} of the closed-spot dilation D_{ϵ}(X), the union of all closed ℓ_{∞}-discs centred at points of X, with radius ϵ/2; the same holds for X′. This fact, for which we have partial theoretical results not covering the critical values ϵ = 2, 3, provides a strong link with “mathematical morphology” (D_{ϵ} being a particular “dilation operator”, cf. [13]) and with the “size homotopy groups” introduced in [6].

It should be noted that (here, as in [12]) various notions appear in two versions, the directed case versus the symmetric (or reversible) one, as in the opposition category-groupoid; such opposition will often be marked by a prefix, ↑ (or “d-”) versus ! (or “r-”), affecting the (historically) secondary notion. The term directed is preferred to ordered or oriented, which might be misleading.

Some basic facts of Category Theory will be frequently used (cf. [19, 1]). Limits in a category extend cartesian products and projective limits; all of them can be constructed from products and equalisers; when all limits exist, the category is said to be complete. Dually, colimits extend sums and injective limits, and can be constructed from sums and coequalisers; a category having all colimits is cocomplete. Left adjoint functors preserve all the existing colimits, while right adjoints preserve limits. The notion of cartesian closed category - having an internal hom linked by adjunction with the cartesian product - is also used.

1. Symmetric combinatorial models

We start considering the combinatorial models which we are going to use, first in the symmetric case and then in the directed one (next section).

A simplicial complex, also called here a combinatorial space or c-space, is a set X equipped with a set !X ⊂ P_{f}X of distinguished finite subsets of X, called linked parts (or simplices), which contains the empty subset, contains all singletons and is down closed: if ξ is linked, any subset ξ′ is so. A morphism of simplicial complexes, or map, or combinatorial mapping f: X → Y is a mapping between the underlying sets which preserves the linked sets: if ξ is linked in X, then f(ξ) is linked in Y.

As easily seen and well-known, the category Cs of combinatorial spaces is complete, cocomplete and cartesian closed ([4]; [10], Section 1). In particular, the linked parts of a product ∏ X_{i} are the finite subsets of all products ∏ ξ_{i} of linked parts; the exponential Hom(A, Y) = Y^{A} characterised by the exponential law Cs(X × A, Y) = Cs(X, Y^{A}), is given by the set of maps Cs(A, Y), equipped with the structure where a finite subset φ of maps f: A → Y is linked whenever, for all α linked in A, φ(α) = ⋃ f(α) is linked in Y.

The forgetful functor | − |: Cs → Set has a left adjoint D and a right adjoint C: the discrete structure DS is the finest (smallest) on the set S (only the empty subset and the singletons are linked), while the chaotic structure CS is the coarsest such (all finite parts are linked). Also D has a left adjoint, the functor

π_{0}: Cs → Set,  π_{0}(X) = |X|/∼ ,  (1)

produced by the equivalence relation ∼ spanned by {x, x′} ∈ !X. A non-empty c-space X is said to be connected (or path-connected, equivalently) if π_{0}(X) is a point; π_{0} is called the functor of connected components (or path-components). Any object is the sum of its connected components. (Note that all these properties are simpler and less diversified than for topological spaces.)

A subobject X′ ≺ X is a subset equipped with a combinatorial structure making the inclusion i: X′ → X a map; equivalently, !X′ ⊂ !X (this is the usual notion of simplicial subcomplex [23]). The subobjects of X form a complete lattice, where ∩X_{i} (resp. ∪X_{i}) is the intersection (resp. union) of the underlying subsets, with structure ∩!X_{i} (resp. ∪!X_{i}). More particularly, a (combinatorial) subspace, or regular subobject X′ ⊂ X, is a subobject with the induced structure: a part of X′ is linked if and only if it is so in X (it is the initial structure for i: X′ → X, i.e. the coarsest making i a map); any intersection or union of subspaces is a subspace. An equivalence relation R in X produces a quotient X/R, equipped with the finest structure making the projection X → X/R a map: a subset of the quotient is linked if and only if it is the image of some linked part of X.

A simpler corpus of models, often used in applications under various equivalent forms, is the category Tol of tolerance sets, equipped with a reflexive and symmetric relation x!x′; the maps preserve this relation. Equivalently, one can consider simple reflexive unoriented graphs (as more used in combinatorics), or adjacency relations, symmetric and anti-reflexive (as used in digital topology, cf. [16, 17]). The forgetful functor t: Cs → Tol takes the c-space X to the tolerance set over |X|, with x!x′ iff {x, x′} ∈ !X. It has a left adjoint d and a right adjoint c; we are more interested in the latter: for a tolerance set A, cA is the coarsest combinatorial space over A inducing the relation ! (a finite subset is linked iff all its pairs are !-related); we shall always identify a tolerance set A with the combinatorial space cA. Thus, Tol becomes a full reflective subcategory of Cs, consisting of those c-spaces where a finite subset is linked if and only if all its parts of two elements are so. The embedding c preserves all limits and is closed under subobjects; in particular, a product of tolerance sets, in Cs, is a tolerance set. Note that this embedding of Tol in Cs clashes with the picture of a tolerance set as a graph (which would rather suggest the skeletal embedding d, where the maximal linked subsets are the linked pairs of points).

Cs is a cartesian closed subcategory of the topos !Smp = Set^{!Δ^{op}} of symmetric simplicial sets, or presheaves on the category of positive finite cardinals [n] = {0, ..., n} [12]. The realisation C: !Δ → Cs of cardinals as codiscrete combinatorial spaces (all subsets are linked) yields a canonical embedding

c: Cs →!Smp,  (cA)_{n} = !Smp(C[n], A),  (2)

where (cA)_{n} is the set of [n]-words of A contained in some linked part; c identifies a combinatorial space with a simple symmetric simplicial set: each item is determined by the family of its vertices. Similarly, Tol is the cartesian closed subcategory of simple presheaves, in the topos !Smp_{1} of 1-truncated symmetric simplicial sets.

The category Cs_{∗} of pointed combinatorial spaces is also complete and cocomplete.

2. Directed combinatorial models

There is a parallel world of directed structures (studied in [12]), where unoriented graphs are replaced by the oriented ones, distinguished subsets by distinguished sequences, and so on.

A directed simplicial complex, or directed combinatorial space, or d-space, is a set X equipped with a set of linked words x = (x_{1}, …, x_{p}) (finite sequences in X) which: contains the empty sequence, contains all unary words (identified with points of X) and is closed under omitting or repeating entries. A morphism, or map, in the category ↑Cs of d-spaces is a mapping which preserves linked words.

Again, ↑Cs has all limits and colimits, and is cartesian closed. Hom(X, Y) = Y^{X} is the set of maps, with the following directed combinatorial structure:

- a word f in ↑Cs(X, Y) is linked if, for every word g = (g_{1}, …, g_{p}) obtained by (possibly) repeating terms of f and every linked word x = (x_{1}, …, x_{p}) of X (of the same length), the word g(x) = (g_{1}(x_{1}), …, g_{p}(x_{p})) is linked in Y.

Also here we have a much simpler corpus of models: a step set has a step relation (or precedence relation) ≺, only assumed to be reflexive, and amounts to a simple reflexive directed graph. Their category Stp is again complete, cocomplete and cartesian closed, with f ≺ g whenever x ≺ x′ implies f(x) ≺ g(x′).

↑Cs has a canonical embedding in the presheaf category Smp = Set^{Δ^{op}} of (ordinary) simplicial sets, as a cartesian closed subcategory; the embedding is produced by the obvious realisation o: Δ → ↑Cs of ordinals as d-spaces (the linked words being the increasing ones)

c: ↑Cs → Smp,  (cA)_{n} = Smp(o[n], A),  (3)

which identifies a directed combinatorial space with a simple simplicial set. Similarly, Stp is the cartesian closed subcategory of simple presheaves, in the topos Smp_{1} of 1-truncated simplicial sets (or reflexive directed graphs).

3. Intrinsic homotopy theories for simplicial complexes

The geometric realisation of a simplicial complex is generally of limited interest in the applications considered here (as motivated in Section 11). We use instead intrinsic homotopy and homology tools, partly known and partly developed in [10, 12]; we recall now briefly the construction of the 1-dimensional homotopical tools, only hinting at the higher dimensional ones.

A simplicial complex X has a classical edge-path groupoid EX ([23], 3.6), isomorphic to the fundamental groupoid of the geometric realisation. An edge path is a finite non empty sequence a = (a_{0}, …, a_{p}) of points of X, where each pair {a_{i−1}, a_{i}} is a linked subset; it goes from ∂^{−}a = a_{0} to ∂^{+}a = a_{p}. Given a consecutive b = (b_{0}, …, b_{q}), with a_{p} = b_{0}, their concatenation is a + b = (a_{0}, …, a_{p}, b_{1}, …, b_{q}). We obtain a small involutive category EX, with objects the points of X and reversion −a = (a_{p}, …, a_{0}).

Two edge paths a, b are said to be simply equivalent if they only differ by the repetition of a point, or can be “deformed one into the other along a ternary linked word”, i.e. if they can be expressed as below

c + (x, y, z) + d,  c + (x, z) + d,  (4)

(or symmetrically) where c, d are paths and (x, y, z) is a linked word. The equivalence relation ∼ generated by simple equivalence is a congruence, and the quotient EX = EX/∼ is the edge-path groupoid of the simplicial complex X (with inverses −[a] = [−a]) .

More generally, an intrinsic homotopy theory for simplicial complexes, with higher homotopy groups and a fundamental groupoid Π_{1}X deriving from a path functor P: Cs → Cs, has been developed in [10]; and Π_{1}X is proved to be isomorphic to EX ([10], 2.10).

Let us briefly recall this construction. The integral line Z, or combinatorial line, is the set of integers equipped with the tolerance structure of contiguity, i!j if |i − j| ⩽ 1. A path in X is a morphism a: Z → X of simplicial complexes which is eventually constant at the left and at the right. In other words, it is a sequence a = (a_{i})_{i∈Z} whose subsets {a_{i−1}, a_{i}} are linked in X, which moreover admits a support ρ = [ρ^{−}, ρ^{+}], i.e. a finite integral interval such that a_{i} is constant for i ⩽ ρ^{−} as well as for i ⩾ ρ^{+} (a amounts thus to an edge path with “unspecified” support). The faces of the path a, or endpoints, are the points where it stabilises: ∂^{−}a = a(ρ^{−}) and ∂^{+}a = a(ρ^{+}).

The path object P X ⊂ X^{Z} is the set of paths in X, with the c-structure induced by the exponential X^{Z}; explicitly, this means that a finite subset α of paths a: Z → X is linked if and only if all the subsets α({i − 1, i}) = ⋃_{a∈α}{a_{i−1}, a_{i}} are linked in X. The mappings ∂^{−}, ∂^{+}: P X → X are combinatorial.

A homotopy φ: f → g: X → Y is a map φ: X → P Y such that ∂^{−}φ = f, ∂^{+}φ = g. The fundamental groupoid Π_{1}X is now defined by equivalence classes of paths, modulo homotopy with fixed endpoints.

One should note that in Cs there is no standard interval, nor cylinder functor (the endofunctor P has no left adjoint, since it only preserves finite products). Similarly, there is no standard circle on which all loops might be parametrised, but rather a system of k-point combinatorial circles C_{k} (k ⩾ 3), such that each loop can be parametrised on a (sufficiently large) circle of this family; namely, C_{k} = Z/≡_{k} is the quotient c-space of the integral line up to the congruence modulo k, a c-space formed by the vertices of a k-gon with distinguished parts contained in contiguous pairs. (All C_{k} are tolerance sets, except C_{3}: its three points are pairwise linked, yet the total subset is not distinguished).

Even more generally, higher fundamental groupoids for symmetric simplicial sets have been introduced in [12], and proved to be left adjoint to higher symmetric nerves M_{n}: n−Gpd → !Smp; thus, each functor Π_{n}: !Smp → n−Gpd preserves all colimits, a strong van Kampen property. But these results will not be used here.

The directed case is similar. Let X be a directed simplicial complex; in an edge path a = (a_{0}, …, a_{p}), each pair (a_{i−1}, a_{i}) is a linked word; concatenation and equivalence are defined as above, but there is no reversion, so that we obtain an edge-path category ↑EX = ↑EX/∼. A directed homotopy theory for simplicial sets has been studied in [12]. It has fundamental n-categories ↑Π_{n}X, left adjoint to higher nerves N_{n}: n−Cat → Smp. The functor of directed paths ↑P X ⊂ X^{↑Z} derives from the directed integral line ↑Z with the precedence relation of consecutivity, i ≺ j if 0 ⩽ j − i ⩽ 1. The k-point directed circle ↑C_{k} = (↑Z)/≡_{k} (k ⩾ 3) is the quotient d-space; it is always a step set, with the induced precedence relation ([i] ≺ [i], [i+1]).

4. Image analysis and combinatorial homotopy

An image will be modelled by a metric space, generally a subspace of some R^{n}. For general reasons which will - in part - appear below, a metric will be allowed to take values in [0, ∞] and not assumed to be definite positive (so that the axioms reduce to: d(x, x) = 0, d(x, y) + d(y, z) ⩾ d(x, z), d(x, y) = d(y, x)). These objects form the category Mtr of (generalised) metric spaces and weak contractions, which is complete and cocomplete (essentially, because ∞ is allowed).

A metric space X has a family of combinatorial structures t_{ϵ}X, at resolution ϵ ∈ [0, ∞], where a finite subset ξ ⊂ X is linked iff its points satisfy the condition d(x, x′) ⩽ ϵ; in other words, t_{ϵ}X is a tolerance set, defined by the relation x!x′ iff d(x, x′) ⩽ ϵ. We have thus a family of forgetful functors t_{ϵ}: Mtr → Tol ⊂ Cs; the case ϵ = ∞ gives the chaotic tolerance structure, while ϵ = 0 gives the equivalence relation d(x, x′) = 0 associated to the generalised metric (the discrete structure on X, if d is definite positive).

In Mtr, a product ∏ X_{i} has the ℓ_{∞}-metric, given by the least upper bound d(x, y) = sup_{i} d_{i}(x_{i}, y_{i}); in other words, this precise metric must be used if we want to “assess” a mapping with values in a product by its components: f: Z → ∏ X_{i} is a weak contraction if and only if all its components f_{i}: Z → X_{i} are so.

The functors t_{ϵ}: Mtr → Cs preserve all limits. Unless differently stated, the real line R has the standard metric and the tolerance structure t_{1}R, with x!x′ iff |x − x′| ⩽ 1; the integral line Z (Section 3) has the induced structure. The real n-space R^{n} has the product structure, defined by the ℓ_{∞}-metric max_{i} |x_{i} − y_{i}|; its linked parts are the finite subsets of elementary cubes ∏_{i} [x_{i}, x_{i} + 1].

An edge-path in the metric simplicial complex t_{ϵ}X is a finite sequence of points (x_{0}, …, x_{p}) with d(x_{i−1}, x_{i}) ⩽ ϵ (i = 1, …, p). The homotopy theory of simplicial complexes produces thus, for a pointed metric space X and for each ϵ ⩾ 0, a fundamental group at resolution ϵ, π_{1}^{ϵ}(X) = π_{1}(t_{ϵ}X) (which, of course, does not depend on the base point if X is ϵ-path connected). To explain its interest, we state here some results, proved in Section 10 (c) by means of a van Kampen theorem and a study of “telescopic homotopies” (other computations can be found in [Gr1], Section 7).

The ℓ_{∞}-metric space X ⊂ R^{2} represented below

\begin{matrix}X = T \ Y & T = [0, 11] × [0, 5], & Y = A ∪ B ∪ C, \\ A = ]1, 4[×]1, 4[, & B = [4, 8]×]1, 2[, & C = ]8, 10[×]1, 3[, \end{matrix}  (5)

is ϵ-path connected as soon as ϵ > 0, but its fundamental group π_{1}^{ϵ}(X) at resolution ϵ varies with the latter, as follows (Z ∗Z denotes the free group on two generators)

\begin{matrix}Z & (0 < ϵ < 1), & Z ∗Z & (1 ⩽ ϵ < 2), \\ Z & (2 ⩽ ϵ < 3), & \{∗\} & (3 ⩽ ϵ ⩽ ∞). \end{matrix}  (6)

It detects thus: one hole (corresponding to Y) at resolution 0 < ϵ < 1; two holes (corresponding to A and C) for 1 ⩽ ϵ < 2 (when B can be jumped over by paths); one hole again (corresponding to A) at resolution 2 ⩽ ϵ < 3; and a simply connected object at resolution ϵ ⩾ 3. We can therefore distinguish among: one single basin (or island) Y; or two basins A, C connected by a bridgeable channel (two islands connected by an isthmus); or one basin A with a negligible appendix; or no relevant basin at all. Of course, the choice of the resolution(s) of interest might be dictated by the application (e.g., what threshold we want to fix for a lake or an island); but again, the whole analysis is of interest and the critical values of its variation (1, 2,

3) detect relevant metric aspects of the configuration. (For critical values, see [10], Section 7).

It is also of interest for computer graphics and image processing that our analysis of the object above can be given much in the same way on a finite digital model, as one can get from a scanning procedure at a fixed resolution ρ small with respect to the dimensions of our object. Take, for instance, the trace of X on a lattice L_{ρ} = ρZ × ρZ = {(ρi, ρj) | i, j ∈ Z} at resolution ρ = k^{−1}, for an integer k ⩾ 2 (as in figure (b) of the Introduction). The metric space X′ = X ∩ L_{ρ} is totally disconnected at resolution ϵ < ρ; it is ϵ-path connected for ϵ ⩾ ρ, where the group π_{1}^{ϵ} gives the same results as above.

(For ρ = 1, all this is still true, but the first case in (6) is empty. If ρ^{−1} is not an integer, the previous results have a marginal variation, due to the interference of L_{ρ} with the boundary of X in R^{2}. However, this effect is rather artificial, due to a hybrid definition of X′ as the discrete trace of a given “continuous space”. Naturally, as well as practically, we should rather start from an explicit description of X′ in terms of points of the grid, as one would get from a scanner.)

Similarly, figure (d) (resp. (e)), a metric subspace of R^{2}, is viewed by the fundamental ϵ-group as a circle (resp. a “figure 8”) at resolution 1 ⩽ ϵ < 8, then as a trivial object

while both figures (f), (g), are analysed as a circle for 1 ⩽ ϵ < 2, and a “figure 8” for 2 ⩽ ϵ < 8, showing how a small resolution is sensitive to “errors”

Finally, let us note that the euclidean ℓ_{2}-metric of the plane, being invariant by rotation, might seem to be more adequate for the present applications. This is not necessarily true, since a scanning procedure can introduce privileged directions, as above. Computation of fundamental groups is easier in the ℓ_{∞}-metric, where one can take full advantage of cartesian products, yet also possible in the ℓ_{p}-metrics (cf. [10], 7.4-5).

5. Directed images

We study now, in the next three sections, some applications of the fundamental category ↑Π_{1}X of a directed simplicial complex (Section 3, here; [12]) to the analysis of “directed images”. (In [12], 4.5, there was a brief hint at such problems, based on step metric spaces; the present approach is somewhat different and more adequate, as remarked at the end of Section 7).

A directed image will be modelled by a generalised, asymmetric metric space in the sense of Lawvere [18], also called here a directed metric space, or d-metric space. It is a set X equipped with a d-metric δ: X × X → [0, ∞], satisfying the axioms

δ(x, x) = 0,  δ(x, y) + δ(y, z) ⩾ δ(x, z).  (7)

(If the value ∞ is forbidden, this notion is often called a quasi-pseudo-metric, as in [15]; but including ∞ has various structural advantages, e.g. the existence of all limits and colimits. This structure is very natural: as motivated in [18], it amounts to a small category enriched over a special monoidal category, with objects t ∈ [0, ∞], arrows t ⩾ t′ and tensor product t + t′; d(x, y) is then the enriched hom of X and the axioms above correspond to assigning units and composition; weak contractions amount to enriched functors. Within the theory of enriched categories, the interest of all this comes from the links between profunctors and Cauchy completion, cf. [18].)

Taking as morphisms, again, the weak contractions, the category ↑Mtr of these d-metric spaces has canonical functors

s_{ϵ}: ↑Mtr → Stp ⊂ ↑Cs,
s_{ϵ}(X, δ) = (X, ≺_{ϵ}),  x ≺_{ϵ} x′ ⟺ δ(x, x′) ⩽ ϵ. (8)

Again, a product in ↑Mtr has the ℓ_{∞} d-metric δ(x, y) = sup_{i} δ_{i}(x_{i}, y_{i}), and the functors s_{ϵ}: ↑Mtr → ↑Cs preserve all limits. A path in the d-metric step set s_{ϵ}X is based on a finite sequence of points (x_{0}, …, x_{p}) with x_{i−1} ≺_{ϵ} x_{i}, i.e. δ(x_{i−1}, x_{i}) ⩽ ϵ for i = 1, …, p. The fundamental category of a d-metric space, at resolution ϵ, is ↑Π_{1}^{ϵ}(X) = ↑Π_{1}(s_{ϵ}X).

A d-metric space can have non-reversible paths (detecting streams) and nonreversible loops (detecting vortices). Consider for instance the directed real circle ↑S^{1}, with d-metric δ(x, x′) equal to the length of the counter-clockwise arc from x to x′. Then, at any point x, the fundamental monoid ↑π_{1}^{ϵ}(X, x) = ↑Π_{1}^{ϵ}(X)(x, x) is isomorphic to the additive monoid N for ϵ < π, and trivial otherwise. (The k-point directed circle ↑C_{k} defined at the end of Section 3 can be embedded as a regular k-gon in s_{ϵ}(↑S^{1}), with ϵ = 2π/n.)

From a practical point of view, a d-metric on a directed image may be not easy to define and visualise, directly. This is why we prefer to derive it, either from a preordered metric space (Section 6) or - more generally - from a step metric space (Section 7).

6. Preordered images

Directed images of a simple type can be represented by a preordered metric space X = (X, d, ⩽). Their category pMtr (with monotone weak contractions) will be embedded in d-metric spaces, whence - at a given resolution ϵ < ∞ - in step sets

U: pMtr → ↑Mtr,  (X, d, ⩽) ↦ (X, δ),
δ(x, x′) = d(x, x′) if x ⩽ x′, δ(x, x′) = ∞, otherwise;
s_{ϵ}: pMtr → Stp,  x ≺_{ϵ} x′ ⟺ (x ⩽ x′ and d(x, x′) ⩽ ϵ).

(9)

(Note that directed images with vortices cannot be represented in this way, since it is easy to see that in s_{ϵ}X each loop is reversible; note also that s_{∞}UX is a chaotic step set, independently of the relation ⩽; we shall generally omit this case.) Such embeddings are not full - as we miss structural information - but preserve all limits. The fundamental category of a preordered metric space, at resolution ϵ, will thus be ↑Π_{1}^{ϵ}(X) = ↑Π_{1}(s_{ϵ}X).

Now, ↑R will denote the real d-line, with the standard metric and the standard order, the derived d-metric and (also) the derived step-structure s_{1}(↑R): x ⩽_{1} x′ iff 0 ⩽ x′ − x ⩽ 1 (the integral d-line ↑Z has the induced structures). The real d-space ↑R^{n} has the product structure, defined by the product order and the ℓ_{∞}-metric; linked words are monotone and contained in an elementary cube ∏_{i} [x_{i}, x_{i} +1]. The lattice operations ∨, ∧: ↑R^{2} → ↑R (max, min) are monotone weak contractions for the ℓ_{∞} d-metrics, and step maps for all structures s_{ϵ}; the same holds for translations, but not for sum, opposite and product.

Let us consider again the ℓ_{∞}-metric space X = T \ Y ⊂ R^{2}, with Y = A ∪ B ∪ C (as in (5)), equipped now with the following preorder ≺ (representing, for instance, a slope as in fig. (k))

(x, y) ≺ (x′, y′) ⟺ (x, x′ ⩽ 5; or 5 ⩽ x ⩽ x′ ⩽ 7; or x, x′ ⩾ 7).  (10)

For ϵ > 0, X is ϵ-connected (i.e., the equivalence relation generated by ≺_{ϵ} is chaotic); its fundamental category at resolution ϵ < ∞ varies with the resolution. With reference to the points a = (0, 3), b = (11, 3), the set ↑Π_{1}^{ϵ}(X)(a, b) is thus

2 arrows (0 < ϵ < 1),  |Z| × |Z| (1 ⩽ ϵ < 2),
|Z|  (2 ⩽ ϵ < 3),  {∗}  (3 ⩽ ϵ < ∞), (11)

(writing |Z| for the set of integers, without algebraic structure). On the other hand, ↑Π_{1}^{ϵ}(X)(b, a) is empty for 0 ⩽ ϵ < ∞.

This detects a stream from left to right (for ϵ > 0). There is one island Y provoking a stream-bifurcation, at resolution 0 < ϵ < 1. Then, for 1 ⩽ ϵ < 2, we find two islands A, C linked by a broken isthmus B; both islands are in still water, at different levels since there are reversible loops around each, but the loops around A must precede the ones around C. Finally, we have one island A at resolution 2 ⩽ ϵ < 3; and no relevant island for ϵ ⩾ 3. As in the symmetric case, this analysis can be given much in the same way on a finite model X′ = X ∩ L_{ρ}.

With a different order, the metric subspaces Y, Z of the plane

(x, y) ≺ (x′, y′) ⟺ |y′ − y| ⩽ x′ − x,  (12)

have fundamental categories with no arrows from b to a, and

↑Π_{1}^{ϵ}(Y)(a, b):  3 arrows (0 < ϵ < 1),  1 arrow (1 ⩽ ϵ < ∞),
↑Π_{1}^{ϵ}(Z)(a, b):  4 arrows (0 < ϵ < 1),  1 arrow (1 ⩽ ϵ < ∞),

(13)

detecting, at sufficiently fine resolution (0 < ϵ < 1) two islands in a stream, either at comparable levels or at different levels, respectively. This analysis is quite similar to the one given in [5], fig. 14, for a similar object viewed as a model of execution paths of concurrent automata: a topological space equipped with a “local order” (an open covering whose subsets are coherently ordered).

Ordered metric spaces can also be used to model space-time. Interpreting the examples above, Y and Z, in a classical sense, with fixed frame and bounded velocity, one can view the abscissa as time, the ordinate as position in a 1-dimensional space, the order as the possibility of going from (x, y) to (x′, y′) with velocity ⩽ 1. The two forbidden rectangles are now obstacles in the line, with a limited duration. Coordinates are expressed with respect to a “material rest frame”, linked with the physical 1-dimensional body under examination; in this frame there is a finite speed limit, settled at 1 by a suitable choice of units for time and length. (The same description also makes sense in a relativistic model with fixed observer.)

7. Step images

A step metric space X = (X, d, ≺), equipped with a metric and a precedence relation, can model more general directed images, also having non-reversible loops.

The category sMtr of step metric spaces has again a natural embedding in ↑Mtr

U: sMtr → ↑Mtr, (X, d, ≺) ↦ (X, δ),

δ(x, x′) = inf{∑_{i=1,...,n} d(x_{i−1}, x_{i}) | x = x_{0} ≺ x_{1} ≺ … ≺ x_{n} = x′}, (14)

extending the one of pMtr (inf is taken in [0, ∞], and inf(∅) = ∞). ↑S^{1} can be obtained in this way from the (symmetric) geodetic distance and a counter-clockwise precedence relation x ≺_{C} x′ (meaning that the counter-clockwise arc from x to x′ is “small”, in some fixed, arbitrary sense). The fundamental category of a step metric space, at resolution ϵ, is again ↑Π_{1}^{ϵ}(X) = ↑Π_{1}(s_{ϵ}UX).

For example, take now the metric space X (as in (5)) equipped with the following precedence relation (meant to correspond to the same slope as in fig. (k), plus a vortex around C)

\begin{aligned}(x, y) ≺ (x′, y′) & ⟺ & (x, x′ ⩽ 5) or (5 ⩽ x ⩽ x′ ⩽ 7) \\ & & or (7 ⩽ x, x′ ⩽ 11 and (x, y) ≺_{C} (x′, y′)), \end{aligned}  (15)

where ≺_{C} is a counter-clockwise precedence relation around C. With respect to the preorder considered in the previous section, in (10), (11), we obtain different results in two cases, for ↑Π_{1}^{ϵ}(X)(a, b)

1 arrow (0 < ϵ < 1),  |Z| × |N| (1 ⩽ ϵ < 2),  (16)

detecting now, from a to b: one stream, with no bifurcation, at resolution 0 < ϵ < 1; two islands A, C, at different levels, linked by a broken isthmus, with a vortex around the second island, for 1 ⩽ ϵ < 2; one island A at resolution 2 ⩽ ϵ < 3, in still water; no relevant island for ϵ ⩾ 3.

Note that, since here the precedence relation ≺ is not transitive, using the step relation derived at resolution ϵ from the initial metric, instead of δ, i.e. (x ≺ x′ and d(x, x′) ⩽ ϵ), would give less adequate results: e.g., the vortex around C would then be detected at any resolution ⩾ 1.

8. Concurrency and directed homotopy

The interest of using directed homotopical or homological tools to explore the (generally non-reversible) execution paths of concurrent automata has appeared recently (cf. [5, 7, 8, 9]). The fundamental n-category of a directed simplicial complex recalled above can likely be used to explore concurrent automata, in various ways adapted to the mathematical model one chooses. Here, we sketch one possible way, where concurrent automata are represented by Chu-spaces on the set Σ = {−1, 0, 1} = {−, 0, +} (for unstarted, active, done), as motivated by Pratt [21]; we shall use the notation and terminology of this paper (which also gives references for the general theory of Chu-spaces; see also [22]).

In fact, such an object (A, r, X) consists of two sets A (of events), X (of states), and a mapping r: A × X → Σ (viewed as a Σ-valued matrix with row-indices in A and column-indices in X); it produces a precedence relation on X

x ≺_{1} x′ ⟺ (∀a ∈ A, ; 0 ⩽ r(a, x′) − r(a, x) ⩽ 1),  (17)

to which we can associate the edge-path category ↑Π_{1}(X, ≺_{1}) (more generally, the fundamental n-category ↑Π_{n}(X, ≺_{1})). A few elementary examples will show how this can be of use.

(a) Let us start from the free Chu-space on a set of two events A = {a, b}, i.e. F (A) = (A, ev, Σ^{A}), where Σ^{A} is the set of all mappings x: A → Σ and ev: A×Σ → Σ is the evaluation ev(a, x) = x(a).

There are therefore 3^{2} states x: A → Σ, represented by the 9 “faces” (of dimension 0, 1, 2) of a square, as in the left diagram below

\xymatrix{−− \ar[rr]^{0^{−}} \ar[dd]_{−0} &  & +− \ar[dd]^{+0} & • \ar[r] \ar[d] \ar[dr] & • \ar[r] \ar[d] \ar[dr] & • \ar[d] \\  & 00 &  & • \ar[r] \ar[d] \ar[dr] & • \ar[r] \ar[d] \ar[dr] & • \ar[d] & · \ar[r] \ar[d] & a \\ −+ \ar[rr]_{0+} &  & ++ & • \ar[r] & • \ar[r] & • & b}  (18)

its vertices are the 4 pure states x: A → {−, +} = {−1, 1}, each represented by a point (x_{a}, x_{b}) ∈ {−1, 1}^{2}, specifying whether the events a, b are unstarted or done; its edges in direction a (or b) correspond to operating the single event a (or b), while the whole square (labelled 00) corresponds to operating both events.

The associated precedence relation on the set of states X = Σ^{A} is represented in the second diagram above, as a simple directed graph; the generic hom-set ↑Π_{1}(X, ≺_{1})(x, x′) of the fundamental category has one arrow if x ⩽ x′ (meaning that r(u, x) ⩽ r(u, x′), for u = a, b), no arrow otherwise. Thus, as it happens for any Chu-space free on a set of events, the fundamental category simply amounts to the order relation ⩽ generated by the precedence relation ≺_{1}.

(b) Consider now the Chu-space (A, r, X) obtained from (a) by precluding the possibility of operating both events at the same time: same A = {a, b}, but X = Σ^{A}\{00}

\xymatrix{−− \ar[r]^{0^{−}} \ar[dd]_{−0} & +− \ar[dd]^{+0} & • \ar[r] \ar[d] & • \ar[r] \ar[dr] & • \ar[d] \\  &  & • \ar[d] \ar[dr] &  & • \ar[d] & · \ar[r] \ar[d] & a \\ −+ \ar[r]_{0+} & ++ & • \ar[r] & • \ar[r] & • & b}  (19)

Here, the hom-set ↑Π_{1}(X, ≺_{1})(−−, ++) has 2 arrows: the path through the pure state +− (operate a, then b) and the path through the pure state −+ (operate b, then a) are no longer homotopically equivalent, as they cannot be deformed one into the other, through “operate a and b ”.

(c) Less simply, if we take three events A = {a, b, c} and let X = Σ^{A} \ {000}, taking out of F (A) the state of simultaneous operation of a, b, c, one can see that ↑Π_{1}(X, ≺_{1} )(−−−, +++) has 1 arrow (one can deform any path into any other, moving around 2-dimensional faces; but now the 2-category ↑Π_{2}(X, ≺_{1}) is not trivial.

(d) With A = {a, b, c} and X = Σ^{A} \ {000, ±00, 0 ± 0, 00±}, i.e. preventing the simultaneous operation of any two or three events, ↑Π_{1}(X, ≺ 1)(− − −, + + +) has six arrows, corresponding to the permutations of A.

It is now relevant to note that a general Chu-space C = (A, r, X) is related to the free object F (A) on its underlying set of events by the counit of the adjunction

\begin{matrix}(idA, r^{•}): (A, ev, Σ^{A}) → (A, r, X), \\ r^{•}: X → Σ^{A}, & r^{x} = r(−, x): A → Σ. \end{matrix}  (20)

C is said to be extensional (and viewed as representing a “progress graph” of concurrent processes) if r^{•} is injective, so that we can identify a state x with the corresponding column r^{x} of the matrix r. Then, (A, r, X) is viewed as sculpted from the free object F (A), taking out unwanted states from Σ^{A}; and the fundamental category ↑Π_{1}(X, ≺_{1}) explores a step-subset of the |A|-dimensional cube (Σ^{A}, ≺_{1}), which may no longer be homotopically trivial. (The dual notion, when r_{•}: A → Σ^{X} is injective, is called separable.)

Finally, let us note that the procedure (A, r, X) ↦ (X, ≺ 1) is the object-function of a contravariant functor s_{1}^{∗}: Chu_{Σ} → Stp^{op}, from Chu-spaces to step sets (which is faithful on separable Chu-spaces).

More generally, there is a family of such functors s_{ϵ}^{∗}: Chu_{Σ} → Stp^{op} (0 ⩽ ϵ ⩽ ∞), which can be used to define the n-fundamental categories at resolution ϵ of a Chu-space, ↑Π_{n}^{ϵ}(X) = ↑Π_{n}(X, ≺_{ϵ}), and distinguish the size of singularities. These functors s_{ϵ}^{∗} derive from a contravariant functor m^{∗} with values in the category of preordered metric spaces, and hence of d-metric ones, composed with s_{ϵ}: ↑Mtr → Stp (in (8))

\begin{matrix}m^{∗}(A, r, X) = (X, d, ⩽), & m^{∗}(f, g) = g, \\ d(x, x′) = sup_{a} |r(a, x) − r(a, x′)|, \\ x ⩽ x′ ⟺ (∀a, r(a, x) ⩽ r(a, x′)), \end{matrix}  (21)

δ(x, x′) = sup_{a}( r(a, x′) − r(a, x)), when r(a, x) ⩽ r(a, x′) (∀a),
δ(x, x′) = ∞, otherwise.

(22)

(Note that the preorder ⩽ is an order if and only if (A, r, X) is extensional, if and only if the metric d is definite positive.) We only have to verify that m^{∗} is well-defined on an arbitrary Chu-map (f, g): (A, r, X) → (B, r, Y), consisting of two mappings f: A → B, g: Y → X such that r(a, g(y)) = s(f(a), y) (for a ∈ A, y ∈ Y); then g: Y → X is indeed a weak contraction and monotone:

d(g(y), g(y′)) = sup_{a} |r(a, g(y)) − r(a, g(y′))|
= sup_{a} |s(f(a), y) − s(f(a), y′)|
⩽ sup_{b} |s(b, y) − s(b, y′)| = d(y, y′),

(23)

\begin{matrix}y ⩽ y′ ⇒ (∀a, s(f(a), y) ⩽ s(f(a), y′)) \\ ⇒ (∀a, r(a, g(y)) ⩽ r(a, g(y′)) ⇒ g(y) ⩽ g(y′). \end{matrix}  (24)

9. Images and combinatorial homology

Also the homology at variable resolution H_{n}^{ϵ}(X) = H_{n}(t_{ϵ}X) of a metric subspace X ⊂ R^{n} can be of interest within image analysis, as showed by the examples below. Of course, H_{1}^{ϵ}(X) yields less fine results than the fundamental group (by Hurewicz); but, in higher dimension, homology is generally easier to compute, as the Mayer-Vietoris sequence is much simpler than the higher extensions of van Kampen (cf. Brown-Higgins [3]).

Let us consider, as in (5), the closed region X = T \ Y of the real plane (with the ℓ_{∞}-metric), endowed with the t_{ϵ}-structure (ϵ > 0).

Then it is easy to prove (as indicated in Section 10 (d)) that H_{ϵ}^{0}(X) ≅ Z and H_{n}^{ϵ}(X) = 0 for all n > 1, while H_{1}^{ϵ}(X) gives:

\begin{matrix}Z & (0 < ϵ < 1), & Z^{2} & (1 ⩽ ϵ < 2), \\ Z & (2 ⩽ ϵ < 3), & 0 & (3 ⩽ ϵ ⩽ ∞). \end{matrix}  (25)

the generators being provided by the 1-chains associated to the loops which generate π_{1}^{ϵ}(X). These results give the same analysis of the metric space X as provided by the fundamental group (Section 4). Also here, the finite model X ∩L_{ρ}, as in Section 4, has the same homology groups for ϵ ⩾ ρ (and the same analysis).

Similarly, one proves that the solid metric subspace X′ ⊂ R^{3}

\begin{matrix}X = T′ \ Y′, & T′ = [0, 11] × [0, 5]^{2}, & Y′ = A′ ∪ B′ ∪ C′, \\ A′ = ]1, 4[×]1, 4[^{2}, & B′ = [4, 8]×]1, 2[^{2}, & C′ = ]8, 10[×]1, 3[^{2}, \end{matrix} (26)

equipped with the t_{ϵ}-structure (ϵ > 0), has H_{n}^{ϵ}(X′) = 0 for n ≠ 0, 2, while H_{2}^{ϵ}(X′) gives the same results as in (25).

The analysis is analogous to the previous one, 1 dimension up: our object presents one cavity Y′, at resolution 0 < ϵ < 1; then two cavities A′, C′ connected by a thin channel (1 ⩽ ϵ < 2); or one cavity A′ with a negligible appendix (2 ⩽ ϵ < 3); and finally no relevant cavity, for ϵ ⩾ 3.

10. Computing homotopy and homology

Combinatorial homotopy and homology can be directly computed, without recurring to topological realisations (examined in the next section). We show now how this can be done, by recalling some instruments introduced or studied in [10, 11]: telescopic homotopies and combinatorial versions of the van Kampen and Mayer-Vietoris theorems.

(a) Telescopic homotopies ([10], Section 3). The simplicial complexes Z^{n} and R^{n} are contractible (homotopy equivalent to the singleton). This can be shown by homotopies based on lattice operations, quite different from the usual topological contraction φ: [0, 1] × R^{n} → R^{n}, φ(t, x) = tx.

To begin with, let E denote either the integral line Z or the real line R. There is a simple telescopic homotopy

\begin{matrix}φ: 0 → id: E → E, \\ φ(i, x) = 0 ∨ (i ∧ x), & φ(i, −x) = −φ(i, x) & (x ⩾ 0), \end{matrix}  (27)

whose general path φ(−, x) has a positive support, namely [0, ρ^{+}(x)], with |x| ⩽ ρ^{+}(x) < |x| + 1. (Similarly, any integral or real interval is contractible; and so is any finite product of such intervals.)

Our name comes from the fact that φ can be viewed as a collection of telescopic arms, which stretch down, in the diagram below (for E = Z), at increasing i ⩾ 0; the arm at x stabilises at depth ρ^{+}(x))

… 0 0 0 0 0 0 0 …  (i = 0) … −1 −1 −1 0 1 1 1 …  (i = 1) … −2 −2 −1 0 1 2 2 …  (i = 2) … −3 −2 −1 0 1 2 3 …  (i = 3) . . . . . . . . . . . . . . . . . . . . . . . . . . .  . . . . . . −3 −2 −1 0 1 2 3 …  (x ∈ Z).  (28)

Now, for the n-dimensional space E^{n}, a telescopic homotopy will be any product of 1-dimensional telescopic homotopies (centred at any point) and trivial homotopies. For instance, for n = 2, consider χ = φ × φ (centred at the origin) and ψ = 0_{id} × φ (centred at the horizontal axis)

χ: 0 → id: E^{2} → E^{2},  χ(i, x_{1}, x_{2}) = (φ(i, x_{1}), φ(i, x_{2})),  (29)
ψ: p_{1} → id: E^{2} → E^{2},  ψ(i, x_{1}, x_{2}) = (x_{1}, φ(i, x_{2})).  (30)

Less trivially, to prove that the c-space t_{ϵ}X ⊂ t_{ϵ}R^{2} described in fig. (a) is contractible for ϵ ⩾ 3, we need a generalised telescopic homotopy centred at the horizontal axis, with “variable vertical jumps” 1, 3, 1 (all ⩽ ϵ and adjusted to jump over the singularity Y = A ∪ B ∪ C).

To make this precise, consider the real or integral line t_{ϵ}E, with the t_{ϵ}-structure (ϵ > 0), and a (generalised) telescopic homotopy, with variable jumps, centred at a_{0}

\begin{matrix}φ: p → id: t_{ϵ}E → t_{ϵ}E, \\ φ(i, x) = a_{0} ∨ (a_{i} ∧ x) (x ⩾ a_{0}), & φ(i, x) = a_{0} ∧ (a_{−i} ∨ x) (x ⩽ a_{0}), \end{matrix}  (31)

between the constant map p(x) = a_{0} and the identity; φ is determined by the characteristic sequence (a_{i}), an increasing combinatorial mapping a: Z → t_{ϵ}E with no lower nor upper bound; it is also determined by its centre a_{0} ∈ E and the sequence of jumps s_{i} = a_{i} − a_{i−1} ∈ E (0 ⩽ s_{i} ⩽ ϵ). This homotopy reduces to the standard telescopic homotopy (1) when ϵ = 1 and a_{i} = i.

Coming back to our example, and letting ϵ ⩾ 3, the simplicial complex t_{ϵ}X ⊂ t_{ϵ}R^{2} is telescopic with respect to the horizontal axis, with jumps s_{1} = 1, s_{2} = 3, s_{3} = 1 on the second variable (arbitrarily completed), hence homotopy equivalent to its intersection with the horizontal axis, which is plainly contractible.

(b) A combinatorial van Kampen Theorem ([10], 6.4). Let X = U ∪V be a simplicial complex. If the set R ⊂ |X| is representative in U, V and U ∩ V (i.e., meets all their path-components), then the following diagram of groupoids (with vertices in R and functors induced by the inclusions) is a pushout

[figure: Π_{1}(U ∩ V)|_{R}; Π_{1}(U)|_{R}; Π_{1}(V)|_{R}; Π_{1}(X)|_{R}]  (32)

The proof is similar to the one in R. Brown’s text [2], simplified by the fact that here any n-dimensional path a: Z^{n} → X has a standard decomposition over the elementary cubes ξ of its support in Z^{n}: for each of them, because of the hypothesis X = U ∪ V, a(ξ) is linked in U or in V; if it is so in both, then it is also linked in U ∩ V. (In the topological case one constructs a non-standard decomposition, invoking the Lebesgue covering theorem).

A similar result holds for the fundamental category of directed simplicial complexes.

(c) Computations. We are now able to compute π_{1}^{ϵ}(X) for the metric space X = T \Y of fig. (c), proving the results stated in 4.2 (one would proceed similarly for fig. (a)).

X is a closed region of the real plane (with the ℓ_{∞}-metric), endowed with the t_{ϵ}-structure. To apply the combinatorial van Kampen theorem, we shall use a fixed U = {(x, y) ∈ X | y > 1} ⊂ X (the dotted region of fig. (q)) and a variable subspace V depending on the resolution. U is t_{ϵ}-telescopic with respect to the line y = 5, with constant jump s_{i} = ϵ, hence contractible.

(i) If 0 < ϵ < 1, X is covered by U (as above) and V = {(x, y) ∈ X | y < 2} (in fig. (r)); the latter is contractible (use again a constant jump s_{i} = ϵ), while U ∩ V = ([0, 1]×]1, 2[) ∪ ([10, 11]×]1, 2[) has two connected components, which are contractible. Taking as a representative subset R = {(0, 3/2), (10, 3/2)}, one deduces that the fundamental group π_{1}^{ϵ}(X) is the free group on one generator, represented by a loop around A ∪ B ∪ C.

(ii) Let 1 ⩽ ϵ < 2. Take V = {(x, y) ∈ X | y < 3}, which is (connected and) t_{ϵ}-telescopic with respect to the horizontal axis (with jumps s_{i} = 1). Thus U, V are contractible, while U ∩ V has three connected components, all contractible. Choosing a representative point in each of them, e.g. R = {(0, 2), (4, 2), (10, 2)}, one falls in the same computation of the topological fundamental groupoid of the “figure 8”; thus, π_{1}^{ϵ}(X) is the free group on two generators, represented by two loops, one around A and the other around C.

(iii) Let 2 ⩽ e < 3. Take V = {(x, y) ∈ X | y < 4}, which is t_{ϵ}-telescopic with respect to the axis y = 0, with vertical jumps s_{1} = 1, s_{2} = 2, s_{3} = 1 (to jump over B∪C). Thus, U and V are contractible while U ∩V has two contractible components. π_{1}^{ϵ}(X) is the free group on one generator, represented by a loop around A.

(iv) Finally, for ϵ ⩾ 3, we have already seen that X is contractible.

(d) The Mayer-Vietoris sequence ([23], ch. 4). A simplicial complex X = U ∪ V has the usual exact M-V sequence (with the obvious meaning of round and square brackets)

\xymatrix{… \ar[r] & H_{n}(U ∩ V) \ar[r]^{(i_{∗},j_{∗})} & (H_{n}U) ⊕ (H_{n}V) \ar[r]^{[u_{∗},−v_{∗}]} & H_{n}X \ar[r]^{Δ} & …} (33)

the maps i: U ∩ V → U, j: U ∩ V → V, u: U → X, v: V → X are inclusions, and the connective Δ is easily described.

The homology of the family of simplicial complexes t_{ϵ}X (ϵ > 0) considered above (in (c)) can now be computed with the same covers, finding the results stated in (25).

11. Topological realisations

Simplicial complexes have various topological realisations, which can be of help in computing their homotopy or homology groups.

(a) Geometric realisation. A simplicial complex X has a classical geometric realisation RX ([23], ch. 3), obtained by gluing together a topological simplex (tetrahedron) Δ(ξ) of dimension n, for each linked part ξ having n + 1 elements, so to preserve the inclusion of linked parts. For a pointed simplicial complex, there is a natural isomorphism π_{n}(X) → π_{n}(RX) between our combinatorial homotopy groups and the classical, topological ones ([10], Thm. 6.6); the similar result for the homology (of non-pointed objects) is well-known (cf. [23]; or [11], 2.2).

But this realisation, theoretically relevant to connect our intrinsic homotopy groups to the classical theory of simplicial complexes, is often not effective for the present applications: excepting a few elementary cases (like R(Z) = R, R(C_{k}) = S^{1}), the geometric realisation of our c-spaces is too big to be of interest. To wit, each elementary square of Z^{2} (a chaotic c-space on four points) is turned into a solid tetrahedron, while Z^{2} is realised as a 3-dimensional pasting of tetrahedra along edges; similarly, Z^{n} is turned into a topological space of dimension 2n − 1. Less “tame” c-spaces, like t_{1}R or a continuous region of the plane, as in fig. (a) or (c), are realised as huge infinite-dimensional spaces.

Homotopically, all this is already a problem, as the realisation may be of scarce help in computing the homotopy groups. Geometrically, it is even worse: regions of Z^{2} and Z^{3}, as produced by scanning a land or a solid object, are important for image analysis; we do not want to reconstruct them as 3- or 7-dimensional spaces, respectively.

(b) McCord realisation. On the other hand, McCord’s “finite type” representation [20] could be of more use. Now, c-spaces are realised as locally finite T_{0} Alexandroff spaces, having again the correct homotopy and homology groups. Finite objects are turned into finite spaces: for instance, the k-point circle C_{k} is represented by a topological space with 2k points, corresponding to the vertices and edges of a k-gon; the vertices are open, while the least neighbourhood of an edge consists of itself and its two vertices.

(c) Spot dilations. Finally, there is a construction which realises simplicial complexes on regions X of R^{n} as topological subspaces of R^{n} itself and often allows for an easy calculation of the fundamental group: a dilation operator, as used in mathematical morphology (cf. [13, 6]), which expands X to a union of discs. The efficiency of this procedure for the c-spaces considered here should be compared with the hugeness of their geometric realisation, infinite-dimensional in the continuous cases; on the other hand, of course, the geometric realisation is general and - theoretically - works for all homotopy groups, while the present comparison is limited (necessarily) to particular metric c-spaces and (presently, at least) to π_{0}, π_{1}.

Let ϵ > 0 and let X be a pointed subset of a normed real vector space E, with metric d. The open-spot dilation D_{ϵ}^{−}(X) and the closed-spot dilation D_{ϵ}(X) of X in E will be the following (pointed) metric subspaces, obtained as a union of d-discs of radius ϵ/2

D_{ϵ}^{−}(X) = D_{ϵ}^{−}(X, d) = {y ∈ E | d(x, y) < ϵ/2 for some x ∈ X} ⊃ X,  (34)
D_{ϵ}(X) = D_{ϵ}(X, d) = {y ∈ E | d(x, y) ⩽ ϵ/2 for some x ∈ X} ⊃ X.  (35)

At present, we are only able to give a general result for π_{1} (and π_{0}) and the first operator D_{ϵ}^{−}. Say that X is t_{ϵ}-closed in E if D_{ϵ}^{−}(X) contains the convex envelope of all linked subsets of t_{ϵ}X, so that there is a continuous mapping, defined on the geometric realisation R(t_{ϵ}X)

f_{ϵ}: R(t_{ϵ}X) → D_{ϵ}^{−}(X),  (36)

extending the identity of X and affine on each simplex Δ(ξ) of the domain. There is then a canonical isomorphism π_{1}(t_{ϵ}X) ≅ π_{1}(D_{ϵ}^{−}X) ([10], thm. 7.5).

The applications are straightforward. Take E_{p} = (R^{2}, d_{p}) with the ℓ_{p}-norm (1 ⩽ p ⩽ ∞) and its continuous region X of fig. (c). Then, X is t_{ϵ}-closed in E_{p}, for p < ∞ and all ϵ different from 1, 2, 3. It would be interesting to have a similar result for the closed-spot dilation, i.e. an isomorphism π_{1}(t_{ϵ}X) ≅ π_{1}(D_{ϵ}X) under sufficiently general hypotheses, satisfied by our examples (where this coincidence appears to hold for the ℓ_{∞}-norm, without exceptions at critical values). Here it is not sufficient to assume that D_{ϵ}X contain the convex envelope of all linked subsets of t_{ϵ}X. In fact, for ϵ = 1, this condition holds for X = {0}∪]1, 2] ⊂ R; but t_{1}X has two path components, while the metric space D_{1}X = [−1/2, 5/2] is connected; it is easy to deduce a 2-dimensional counterexample, with different π_{1}. However, the previous condition might be sufficient for a compact X, which would include cases as the space of fig. (c).

References

[1] F. Borceux, Handbook of categorical algebra 1-3, Cambridge Univ. Press, Cambridge 1994.

[2] R. Brown, Topology, Ellis Horwood, Chichester 1988.

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

[4] S. Eilenberg - G.M. Kelly, Closed categories, in: Proceedings of the Conference on Categorical Algebra, La Jolla 1965, Springer 1966, 421-562.

[5] L. Fajstrup - E. Goubault - M. Raussen, Algebraic topology and concurrency, Preprint 1999. http://www.di.ens.fr/˜ goubault/

[6] P. Frosini - M. Mulazzani, Size homotopy groups for computation of natural size distances, Bull. Belg. Math. Soc. Simon Stevin 6 (1999), 455-464.

[7] P. Gaucher, Homotopy invariants of higher dimensional categories and concurrency in computer science, Math. Struct. in Comp. Science 10 (2000), 481-524.

[8] P. Gaucher, Combinatorics of branchings in higher dimensional automata, Theory Appl. Categ. 8 (2001), No. 12, 324-376 (electronic). http://tac.mta.ca/tac/

[9] P. Gaucher - E. Goubault, Topological Deformation of Higher Dimensional Automata, Preprint 2001. http://www-irma.u-strasbg.fr/˜ gaucher/diCW.ps

[10] M. Grandis, An intrinsic homotopy theory for simplicial complexes, with applications to image analysis, Appl. Categ. Structures 10 (2002), 99-155.

[11] M. Grandis, Combinatorial homology and image analysis, Dip. Mat. Univ. Genova, Preprint 394 (1999). http://www.dima.unige.it/˜ grandis/

[12] M. Grandis, Higher fundamental functors for simplicial sets, Cahiers Topologie Geom. Differentielle Categ. 42 (2001), 101-136.

[13] H.J.A.M. Heijmans, Mathematical morphology: a modern approach in image processing based on algebra and geometry, SIAM Rev. 37 (1995), 1-36.

[14] P.J. Hilton - S. Wylie, Homology theory, Cambridge Univ. Press, Cambridge 1962.

[15] J.C. Kelly, Bitopological spaces, Proc. London Math. Soc. 13 (1963), 71-89.

[16] T.Y. Kong - R. Kopperman - P.R. Meyer, A topological approach to digital topology, Amer. Math. Monthly 98 (1991), 901-917.

[17] T.Y. Kong - R. Kopperman - P.R. Meyer Eds., Special issue on digital topology, Topol. Appl. 46 (1992), No. 3, 173-303.

[18] F.W. Lawvere, Metric spaces, generalized logic and closed categories, Rend. Sem. Mat. Fis. Univ. Milano 43 (1974), 135-166.

[19] S. Mac Lane, Categories for the working mathematician, Springer, Berlin 1971.

[20] M.C. McCord, Singular homology groups and homotopy groups of finite topological spaces, Duke Math. J. 33 (1966), 465-474.

[21] V. Pratt, Higher dimensional automata revisited, Math. Struct. in Comp. Science 10 (2000), 525-548.

[22] V. Pratt, Chu spaces, in: School on Category Theory and Applications (Coimbra, 1999), 39-100, Textos Mat. Ser. B, 21, Univ. Coimbra, Coimbra, 1999.

[23] E.H. Spanier, Algebraic Topology, Mc Graw-Hill, New York 1966.

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

Marco Grandis grandis@dima.unige.it

Dipartimento di Matematica, Università di Genova Via Dodecaneso 35, 16146-Genova, Italy