Homology, Homotopy and Applications, vol.6(1), 2004, pp.439–471

ON THE HOMOLOGY OF SMALL CATEGORIES AND ASYNCHRONOUS TRANSITION SYSTEMS

AHMET A. HUSAINOV

(communicated by Ronald Brown)

Abstract This work is devoted to an interpretation and computation of the first homology groups of the small category given by a rewriting system. It is shown that the elements of the first homology group may be regarded as the equivalence classes of the flows in a graph of the rewriting system. This is applied to calculating the homology groups of asynchronous transition systems and Petri nets. Examples of calculations are given.

Introduction

This paper is devoted to the study of the first homology group of a category with coefficients in a diagram of abelian groups. It was shown in [9] that, for a free category generated by a directed graph, this homology group consists of generalized flows in the graph. In this paper we shall extend this assertion to all small categories. We prove that each member of the first homology group may be interpreted as a class of generalized flows (Theorem 3.2). This result was announced in [8], but the proof was not published.

The most important subject of this paper is concerned with the introduction and calculation of homology groups of concurrent computing models. We use the models which are studied by the theory of categories in [26]. A well known problem is to define homology groups for such models; such homology groups are of interest for computer science. E. Goubault [5] and P. Gaucher [3], [4] have given a definition of homology groups for higher dimensional automata. In the work [11] it was proved that the category of asynchronous transition systems admits a functor into the category of pointed sets over partially commutative monoids. This allows us to introduce a definition for homology groups of asynchronous transition system.

We prove (Theorem 1.2) that if a presentation (E, R) of a partially commutative monoid has no distinct elements a, b, c ∈ E for which ab = ba and bc = cb and ac = ca, then the 2-category Ω(R) related to (E, R) is trivial in the sense of [18].

Using Mitchell’s results we give in Corollary 3.5 conditions under which the homology groups H_{n}( ℂ, F) of a category ℂ are zero for all diagrams F and n ⩾ 3.

Received January 26, 2004, revised October 12, 2004; published on October 18, 2004. 2000 Mathematics Subject Classification: 18G10, 68M14, 55U99, 68Q85. Key words and phrases: Homology of categories, category of asynchronous systems, category of Petri nets. \begin{matrix}c \\ ◯ \end{matrix} 2004, Ahmet A. Husainov. Permission to copy for private use granted.

This allows us to describe all the homology groups of asynchronous transition systems which do not contain triples of mutually independent events (Corollary 5.4).

The homology groups of a category of states augmented by an “infinitely distant state” were studied in the work [11]. The investigation of the homology groups of the augmented category is reduced to studying the homology of partially commutative monoids (Theorem 5.3). Nevertheless we consider mainly the homology of the category of states without the infinitely distant state. In terms of flows we describe the homology groups of the asynchronous transition system for the reader and writer problem. Then we consider integer homology groups for a Petri net. Finally, we calculate the integer homology of the pipeline Petri net.

I am grateful to an anonymous referee and to the Editor for many comments on various versions which have helped to improve this paper.

1. Presentations of categories

Let A be a category. Given objects a, b ∈ ObA denote by A(a, b) the set of all morphisms a → b. Each morphism α ∈ A(a, b) has a domain dom α = a and a codomain cod α = b. We write a →^{α} b or α : a → b if α ∈ A(a, b). We use the notation β∘α (or βα) for the composition of morphisms a →^{α} b and b →^{β} c instead of Mitchell’s αβ. Morphisms α and β are parallel if dom α = dom β and cod α = cod β. In this case (α, β) is called a parallel pair. By analogy with the building of the category of topological spaces and homotopy classes of continuous maps we can consider a “homotopical” category for an arbitrary category if we declare to be homotopic morphisms of some parallel pairs. This leads us to a quotient category notion.

Quotient categories. Let ℂ be a small category. Put ℂ(a, b)^{2} = ℂ(a, b)× ℂ(a, b). The set

P ℂ = ⋃_{a,b∈Ob ℂ} ℂ(a, b)^{2}

thus consists of all parallel pairs in ℂ.

For each parallel pair p = (α, β) we denote by dom p = dom α = dom β their common domain and cod p = cod α = cod β their codomain.

Definition 1.1. A subset Q of P ℂ is called a congruence relation on ℂ if the following conditions hold:

(i) if q = (α, β) ∈ Q, then (f ∘α∘g, f ∘β ∘g) ∈ Q for all morphisms f, g ∈ Mor ℂ satisfying dom f = cod q and cod g = dom q;

(ii) for each pair (a, b) of objects in ℂ the set Q(a, b) = ℂ(a, b)^{2} ∩ Q is an equivalence relation on the set ℂ(a, b).

Definition 1.2. Let ℂ be a small category and Q a congruence relation on ℂ. The quotient category ℂ/Q is a category with the set of objects Ob ℂ, in which the morphism sets ( ℂ/Q)(a, b) for a, b ∈ ℂ are the equivalence classes with respect to Q(a, b) on the sets of morphisms a → b in ℂ.

The map α ↦ π(α) defines a functor π : ℂ → ℂ/Q such that π(α) = π(β) for all (α, β) ∈ Q. If F : ℂ → 𝔻 satisfies the same property, then there is an unique functor F′ : ℂ/Q → 𝔻 such that F′ ∘ π = F.

The functor π is the canonical projection.

Lemma 1.1. Let R ⊆ P ℂ be an arbitrary set of parallel pairs in ℂ and \overline{R} the smallest congruence relation containing R on ℂ. Suppose that π : ℂ → ℂ/\overline{R} is the canonical projection. Let α, β : a → b be a parallel pair with α ≠ β. Then the equality π(α) = π(β) holds if and only if there are morphisms z_{i} with cod z_{i} = b, y_{i} with dom y_{i} = a, and a sequence of pairs (s_{i}, t_{i}) ∈ R ∪ R^{−1}, 1 ⩽ i ⩽ k, such that

\begin{aligned}α & = & z_{1}s_{1}y_{1}, \\ z_{1}t_{1}y_{1} & = & z_{2}s_{2}y_{2}, \\ z_{2}t_{2}y_{2} & = & z_{3}s_{3}y_{3}, \\ & ⋯ \\ z_{k}t_{k}y_{k} & = & β. \end{aligned}  (1)

for some k > 0. The sequence (y_{i}, s_{i}, t_{i}, z_{i}), 1 ⩽ i ⩽ k, will be denoted by (y, s, t, z) : α → β and called a 2-path of length k from α to β. Also we consider the empty 2-path denoted by ( )_{α} from α to α by taking k = 0.

We recommend the paper [25] for a good discussion of 2-paths.

Let R be a set of parallel pairs. The quotient category ℂ/\overline{R} is denoted by ℂ/R. If there is a 2-path (y, s, t, z) : α → β, then we say α and β are equivalent with respect to R and write α ≃ β mod R.

2-categories. B. Mitchell [18] used 2-categories in the study of small categories with Hochschild-Mitchell dimension ⩽ 2. To apply his results [18] we recall the properties of a presentation and the definition of a 2-category.

Definition 1.3. A 2-category is a class of objects, Ob ℂ, together with a family {Hom_{ℂ}(a, b)}_{(a,b)∈Ob ℂ×Ob ℂ} of some small categories. We assume also that there is given for every triple (a, b, c) ∈ Ob ℂ × Ob ℂ × Ob ℂ a functor

∗_{a,b,c} : Hom_{ℂ}(a, b) × Hom_{ℂ}(b, c) → Hom_{ℂ}(a, c)

and for every a ∈ Ob ℂ there is given an object i_{a} ∈ Ob(Hom_{ℂ}(a, a)). We write β ∗α = ∗_{a,b,c}(α, β) for α ∈ Mor(Hom_{ℂ}(a, b)) and β ∈ Mor(Hom_{ℂ}(b, c)). For arbitrary α ∈ Mor(Hom_{ℂ}(a, b)), β ∈ Mor(Hom_{ℂ}(b, c)) and for f ∈ Ob(Hom_{ℂ}(a, b)), g ∈ Ob(Hom_{ℂ}(b, c)) we write g ∗ α = 1_{g} ∗ α, β ∗ f = β ∗ 1_{f}. The objects of the categories Hom_{ℂ}(a, b) are called 1-morphisms and the morphisms of the categories Hom_{ℂ}(a, b) are called 2-morphisms. The functors ∗ have to satisfy the following axioms:

(i) (γ ∗ β) ∗ α = γ ∗ (β ∗ α) for all a, b, c, d ∈ Ob ℂ and for all 2-morphisms α ∈ Mor(Hom_{ℂ}(a, b)), β ∈ Mor(Hom_{ℂ}(b, c)), γ ∈ Mor(Hom_{ℂ}(c, d));

(ii) α ∗ i_{a} = α = i_{b} ∗ α for all a, b ∈ Ob ℂ and α ∈ Mor(Hom_{ℂ}(a, b)).

The operation ∗ is called the horizontal composition. The composition in the categories Hom_{ℂ}(a, b) is denoted by · and called the vertical composition.

Every 2-category ℂ has the category structure where Ob ℂ is the class of objects and Mor ℂ = ⋃_{(a,b)∈Ob ℂ×Ob ℂ} Ob(Hom_{ℂ}(a, b)) is the class of morphisms with the

composition g ∘ f = ∗_{a,b,c}(f, g) for f ∈ Ob(Hom_{ℂ}(a, b)), g ∈ Ob(Hom_{ℂ}(b, c)) and the identity morphisms i_{a} ∈ Ob(Hom_{ℂ}(a, a)). So we write g ∘ f for 1-morphisms instead of g ∗ f and 1_{a} instead of i_{a}.

Remark 1.4. Since the composition ∗_{a,b,c} : Hom_{ℂ}(a, b)×Hom_{ℂ}(b, c) → Hom_{ℂ}(a, c) is functorial, we have the interchange law

(β′ ∗ α′) · (β ∗ α) = (β′ · β) ∗ (α′ · α)

where the point denotes the vertical composition. This is also called the “distributive law” [18] or sometimes the “Godement law”.

Example 1.5. The category Cat of all small categories is the 2-category whose 1-morphisms are functors and 2-morphisms are natural transformations. The composition β ∗ α : g ∘ f → g′ ∘ f′ of natural transformations α : f → f′, β : g → g′ is defined by

β ∗ α = (g′ ∗ α) · (β ∗ f)

where g′ ∗ α and β ∗ f have components (g′ ∗ α)_{a} = g′(α_{a}) and (β ∗ f)_{a} = β_{f(a)}.

A 2-category and 2-paths. We consider the application of 2-categories to quotient categories following B. Mitchell [18]. Let ℂ be a small category and R a set of parallel pairs in ℂ.

For finite sequences x = (x_{1}, ⋯, x_{m}) and y = (y_{1}, ⋯, y_{n}) denote their concatenation by x · y = (x_{1}, ⋯, x_{m}, y_{1}, ⋯, y_{n}) by x · y, and the reverse by \overline{x} = (x_{m}, ⋯, x_{1}). If a sequence (x_{1}, ⋯, x_{m}) consists of morphisms with a common domain d, then for each morphism α : a → d let xα = (x_{1}α, ⋯, x_{m}α). We define similarly αx. For every 2-paths (x, α, β, y) : f → g and (x′, α′, β′, y′) : g → h we let (x′, α′, β′, y′) · (x, α, β, y) = (x · x′, α · α′, β · β′, y · y′). We get a 2-path from f to h. The reverse (\overline{x}, \overline{β}, \overline{α}, \overline{y}) yields a 2-path from g to f. There exists an identity 2-path of length k = 0 from f to f. Hence pairs of morphisms (f, g) which have 2-paths from f to g define an equivalence relation. Moreover, if (x, α, β, y) is a 2-path from f to g, then (xh, α, β, y) is a 2-path from fh to gh and (x, α, β, hy) is a 2-path from hf to hg.

For any pair a, b ∈ Ob ℂ, denote by Ω_{0}(R)(a, b) the set of all 2-paths between the morphisms of ℂ(a, b). The concatenation of 2-paths gives Ω_{0}(R)(a, b) the structure of category. It is the category of paths in a directed graph whose arrows are 2-paths of length 1. For (x, α, β, y) : f → g and (x′, α′, β′, y′) : f′ → g′, define the 2-path f′f → g′g as

(x′, α′, β′, y′) ∗ (x, α, β, y) = (x, α, β, g′y) · (x′f, α′, β′, y′) ,

when f′f and g′g are defined. The operation ′∗′ gives Ω_{0}(R) a structure of category, but the interchange law does not hold in it and the horizontal composition is not functorial. Nevertheless, this operation becomes functorial on a quotient category of Ω_{0}(R).

Suppose that R is an antisymmetric and irreflexive relation, i.e. (α, β) ∈ R implies (β, α) ∉ R. A 2-path (x, α, β, y) : f → g is closed if f = g. A closed 2-path (1) is said to be degenerate if k is an even number and if the set {1, 2, ⋯, k} may be partitioned into two element subsets {i, j} such that (α_{i}, β_{i}) = (β_{j}, α_{j}) and x_{i} ≃ x_{j} mod R, y_{i} ≃ y_{j} mod R. Otherwise the closed 2-path is said nondegenerate. If (x, α, β, y) and (x′, α′, β′, y′) are both 2-paths from f to g, then they will be called equivalent if the vertical composition (\overline{x}, \overline{β}, \overline{α}, \overline{y}) · (x′, α′, β′, y′) is degenerate.

Following B. Mitchell [18] we define Ω(R) as the 2-category such that

Ob(Ω(R)) = Ob(Ω_{0}(R)) = Ob ℂ and Mor(Ω(R)) = Mor(Ω_{0}(R)) = Mor ℂ

where the sets of 2-morphisms Hom_{Ω(R)}(a, b)(f, g) consist of the equivalence classes of 2-paths (x, α, β, y) : f → g which inherits the horizontal and vertical compositions. For every a, b ∈ Ob( ℂ) the category Hom_{Ω(R)}(a, b) is a groupoid, since the reverse of a 2-path becomes an inverse for it. If every closed 2-path is degenerate, then Ω(R) is called trivial.

It is easy to see that Ω(R) is trivial if and only if for every 1-morphism f, g : a → b the set Hom_{Ω(R)}(a, b)(f, g) contains at most of one element.

Rewriting systems. Let Γ be a directed graph. We denote by A(Γ) the set of its arrows and by V (Γ) the set of its vertices. If ℂ = PaΓ is the path category in a directed graph Γ and R a set of parallel pairs in PaΓ, then the pair (Γ, R) is called a presentation of the quotient category PaΓ/R. In this case the pair (Γ, R) is also said to be a rewriting system for PaΓ/R.

If the graph Γ has one vertex, then its arrows may be regarded as letters in the alphabet E = A(Γ) and its paths are words w ∈ E^{∗} = PaΓ. In this case the rewriting system is denoted by (E, R) and presents a monoid. Rewriting systems for presentations of categories were applied in [17], [19] to the study of the Hochschild-Mitchell homology of categories.

Definition 1.6. A monoid is said to be partially commutative if it has a presentation (E, R) where E is an arbitrary set and R consists of some pairs (ab, ba) of words with a, b ∈ E and a ≠ b.

Example 1.7. Let E = {a, b, c}, R = {(ab, ba), (bc, cb), (ac, ca)}. This rewriting system presents the free commutative monoid generated by three members. It has the closed nondegenerate 2-path

\begin{aligned}abc & = & bac, \\ bac & = & bca, \\ bca & = & cba, \\ cba & = & cab, \\ cab & = & acb, \\ acb & = & abc. \end{aligned}

Theorem 1.2. Let (E, R) be a rewriting system of a partially commutative monoid M where E is a set and R ⊆ E^{∗} × E^{∗} an antisymmetric and irreflexive relation consisting of some pairs (ab, ba) with a, b ∈ E. If there are no distinct letters a, b, c ∈ E for which (ab, ba) ∈ R ∪ R^{−1} and (bc, cb) ∈ R ∪ R^{−1} and (ac, ca) ∈ R ∪ R^{−1}, then the 2-category Ω(R) is trivial.

Proof. The 2-category Ω(R) has a single object because (E, R) presents a monoid. We will denote this object by M. Words α ∈ E^{∗} are 1-morphisms in Ω(R). Equivalence classes of 2-paths α → β will be 2-morphisms from α ∈ E^{∗} to β ∈ E^{∗}. Every 2-path consists of steps (y_{i}, (a_{i}b_{i}, b_{i}a_{i}), z_{i}) : z_{i}a_{i}b_{i}y_{i} → z_{i}b_{i}a_{i}y_{i} where (a_{i}b_{i}, b_{i}a_{i}) ∈ R ∪ R^{−1}, y_{i} ∈ E^{∗}, z_{i} ∈ E^{∗}. Since Hom_{Ω(R)}(M, M) is a groupoid, it is enough to prove an assertion about that for every α ∈ E^{∗} and β ∈ E^{∗} there is at most one 2-morphism α → β.

We will prove it by induction on the length of α. Suppose that the assertion is true for words of length less than the length of α. Let us suppose that there exists a 2-path α → β. Then the length of α equals the length of β. Let α = aw and β = bw′, for some letter a, b ∈ E and some words w, w′ ∈ E^{∗}.

We consider the case a ≠ b. There are no words of the form cv, with c ∈ E\{a, b}, which are contained in the 2-path α → β; or else we would have (ac, ca) ∈ R ∪ R^{−1} and (bc, cb) ∈ R ∪ R^{−1}.

Hence all morphisms α → β belong to a full subcategory of Hom_{Ω(R)}(M, M) consisting of words of the form av and bv for some words v ∈ E^{∗}. We denote this full subcategory by Ω_{(a,b)}. Let Ω_{a} ⊆ Ω_{(a,b)} be the full subcategory of words av and let Ω_{b} ⊆ Ω_{(a,b)} be the full subcategory of words bv, for all v ∈ E^{∗}. (See Fig. 1.)

[figure: ab ⋯; ba ⋯; a ⋯; b ⋯; α; β; Ω_{a}; Ω_{b}]

Figure 1: A graph containing the 2-paths α → β

The categories Ω_{a} and Ω_{b} are trivial because of the inductive hypothesis. Each 2-path α → β consists of steps av → av′, abv → bav, bv → bv′, bav → abv, for some v, v′ ∈ E^{∗}. Denote by ψ : ab → ba the equivalence class of the path containing the single step (1, (ab, ba), 1) : ab → ba. Every 2-morphism α → β equals a composition of morphisms of forms 1_{a} ∗ η : av → av′, ψ ∗ 1_{v} : abv → bav, 1_{b} ∗ η : bv → bv′, ψ^{−1} ∗ 1_{v} : bav → abv, for some 2-morphisms η in Ω(R).

Because of the distributivity law, for each 2-morphism η : v → v′, we have the following commutative square

abv  ⟶^{ψ∗1_{v}} bav
1_{ab} ∗ η ↓  ↓ 1_{ba} ∗ η
abv′  ⟶^{ψ∗1_{v′}} bav′

It is easy to see from the commutativity of this square that every 2-morphism α → β is the equivalence class of a path which consists of steps

α = \underbrace{av → ⋯ → abu}_{Ω_{a}} ⟶^{(u,(ab,ba),1)} \underbrace{bau → ⋯ → bv}_{Ω_{b}} = β

Since Ω_{a} and Ω_{b} are trivial, it follows from the distributivity law that every two such paths are equivalent.

Now we prove that all closed 2-paths are degenerate. Let α = aw. For each 2path α → α there exists b ∈ E such that this 2-path consists of words which equal either av or bv for some v ∈ E^{∗}. If a = b, then we obtain a 2-path which has the equivalence class a ∗ η : aw → aw, for some η : w → w. Such η is equivalent to a degenerate path by the inductive hypothesis. If a ≠ b, then the equivalence class of the 2-path α → α equals the composition θ · η for some w′ and 2-paths η : aw → bw′, θ : bw′ → aw. Since η and the reverse of θ are equivalent, we have that θ · η is degenerate. Hence Ω(R) is trivial. □

2. Homology groups of a small category

The purpose of this section is to introduce the reader into homology of small categories. We recommend the survey [8] for a deeper study of this theory. Let Set be the category of sets and maps and Ab the category of abelian groups and homomorphisms. A diagram in A on ℂ is a functor ℂ → A from a small category ℂ to a category A. In particular, for each object c ∈ ℂ there is defined the diagram h^{c} : ℂ → Set with h^{c}(a) = ℂ(c, a) for objects a ∈ ℂ. This diagram assigns to any morphism f : a → b the map ℂ(c, f) : ℂ(c, a) → ℂ(c, b) which acts as ℂ(c, f)(g) = f ∘ g ∈ ℂ(c, b).

The category of diagrams in Ab. Let Ab^{ℂ} be the category of diagrams ℂ → Ab in which morphisms are natural transformations. Limits and colimits in the diagram category may be calculated objectwise. Consequently the category Ab^{ℂ} has infinite products, kernels, and cokernels. The following assertion is well-known [7]:

Proposition 2.1. The category Ab^{ℂ} is abelian and has enough projective and injective objects.

Since kernels and cokernels in the diagram category may be calculated objectwise, the sequence of diagrams and natural transformations

0 → F′ →^{η′} F →^{η′′} F′′ → 0.  (2)

is exact if and only if the sequences of abelian groups and homomorphisms

0 → F′(c) →^{η′_{c}} F (c) →^{η′′_{c}} F′′(c) → 0  (3)

are exact for all c ∈ ℂ.

Categories of homological dimension 0. A category is connected if it is not equal to the coproduct of some nonempty categories. A small category is pseudofiltered [16] if its maximal connected subcategories are filtered. It is well known that if a small category ℂ is pseudo-filtered, then the colimit functor colim^{ℂ} : Ab^{ℂ} → Ab is exact, i.e. for an exact sequence (2) the sequence

0 → colim^{ℂ} F′ → colim^{ℂ} F → colim^{ℂ} F′′ → 0  (4)

is exact. U. Oberst [22] put forward the conjecture that if colim^{ℂ} is exact, then ℂ is pseudo-filtered. But this was refuted by J. Isbell [12].

Small categories ℂ for which the functor colim^{ℂ} is exact were characterized by U. Oberst [23], J. Isbell and B. Mitchell [13]. Such categories are called categories of homological dimension 0 [8]. Nevertheless little is known about these categories.

For example, there is a conjecture from J. Isbell and B. Mitchell [14] which is concerned with the exactness of colim^{ℂ} : Ab^{ℂ} → Ab with a fixed point property of ℂ. It is possible that our interpretation of colim_{1}^{ℂ} F (Theorem 3.2) may be helpful for the resolution of this problem.

Satellites of the colimit functor. In general, the sequence (4) is not exact at colim^{ℂ} F′. The homology theory of small categories measures the failure of exactness of this sequence. The theory of Abelian categories is the usual tool for the treatment of this kind of problem.

The exact sequence (2) gives rise to the canonical long exact sequence

⋯ → colim_{n}^{ℂ} F′ → colim_{n}^{ℂ} F → colim_{n}^{ℂ} F′′ → colim_{n−1}^{ℂ} F′ → ⋯
⋯ → colim^{ℂ} F′ → colim^{ℂ} F → colim^{ℂ} F′′ → 0,

which defines a sequence of functors colim_{n}^{ℂ} : Ab^{ℂ} → Ab with the property colim_{0}^{ℂ} = colim^{ℂ}. They are the left satellites of colim^{ℂ}. Since Ab^{ℂ} has enough projectives, the left satellites are isomorphic to left derived functors of the colimit.

The values of the satellites are isomorphic to the homology groups of the chain complex considered below.

For every family {A_{i}}_{i∈I} we denote by in_{i} : A_{i} → ⨁_{i∈I} A_{i} the canonical morphisms into the coproduct. Let ℂ be a small category. Denote by d_{i}^{n}, 0 ⩽ i ⩽ n, the maps assigning to each sequence σ = (c_{0} →^{α_{1}} c_{1} →^{α_{2}} ⋯ →^{α_{n}} c_{n}) of length n the sequence of length (n − 1) defined as follows. The maps d_{i}^{n}, for 0 < i < n, delete objects c_{i}

from c_{0} →^{α_{1}} c_{1} →^{α_{2}} ⋯ →^{α_{n}} c_{n} and insert instead of morphisms c_{i−1} →^{α_{i}} c_{i} →^{α_{i+1}} c_{i+1} the

composition c_{i−1} ⟶^{α_{i+1}∘α_{i}} c_{i+1}. For i = 0 or i = n we let d_{0}^{n}(c_{0} → ⋯ → c_{n}) = c_{1} →^{α_{2}}

c_{2} → ⋯ →^{α_{n}} c_{n} and d_{n}^{n}(c_{0} → ⋯ → c_{n}) = c_{0} →^{α_{1}} c_{1} →^{α_{2}} ⋯ →^{α_{n−1}} c_{n−1}.

Let F : ℂ → Ab be a diagram of abelian groups. The chain complex C_{∗}( ℂ, F) consists of the abelian groups

C_{n}( ℂ, F) = ⨁_{c_{0}→···→c_{n}} F (c_{0}), n ⩾ 0,

(with C_{n}( ℂ, F) = 0 for n < 0) and the homomorphisms (called “boundary operators”)

∂_{n} = ∑_{i=0}^{n+1}(−1)^{i}∂_{n}^{i} : C_{n}( ℂ, F) → C_{n−1}( ℂ, F), n > 0,

where ∂_{n}^{i} is the unique morphism satisfying for each

σ = (c_{0} →^{α_{1}} c_{1} →^{α_{2}} ⋯ →^{α_{n}} c_{n})

the condition

∂_{n}^{i} ∘ in_{σ} = \begin{cases}in_{d_{i}^{n}σ} , & for 1 ⩽ i ⩽ n \\ in_{d_{0}^{n}σ} ∘ F (c_{0} →^{α_{1}} c_{1}) , & for i = 0. \end{cases}

For n ⩾ 0, the homology group H_{n}(C_{∗}( ℂ, F)) = Ker ∂_{n}/ Im ∂_{n+1} is denoted by H_{n}( ℂ, F) and called the n-th homology group of ℂ with coefficients in F. Let F : ℂ → Ab, G : ℂ → Ab be diagrams of abelian groups. A natural transformation η : F → G induces a chain homomorphism C_{∗}( ℂ, F) → C_{∗}( ℂ, G) and so homomorphisms H_{n}( ℂ, F) → H_{n}( ℂ, G), for n ⩾ 0.

Proposition 2.2. [2, Appl.2] The functors H_{n}( ℂ, −) : Ab^{ℂ} → Ab are naturally isomorphic to the left satellites colim_{n}^{ℂ} of the functor colim^{ℂ} : Ab^{ℂ} → Ab.

Kan extensions and relative derived functor of the colimit. Let ℂ and 𝔻 be small categories and S : 𝔻 → ℂ a functor. Let c ∈ Ob ℂ. The comma category S ↓ c is the category with objects the pairs (d, f) with d ∈ Ob 𝔻 and f ∈ ℂ(S(d), c) and with morphisms (d, f) → (d′, f′) the triples (f, f′, g) satisfying f′ ∘ S(g) = f [16]. Consider the functor Ab^{S} : Ab^{ℂ} → Ab^{𝔻} which assigns to every diagram G : ℂ → Ab the diagram G ∘ S : 𝔻 → Ab and to every natural transformation η : G → G′ the natural transformation η ∗ S, where (η ∗ S)_{d} = η_{S(d)}. The functor Ab^{S} has a left adjoint Lan^{S} : Ab^{𝔻} → Ab^{ℂ} which is called the left Kan extension along S [16]. According to [16] for each diagram F : 𝔻 → Ab the diagram Lan^{S} F may be given as (Lan^{S} F)(c) = colim^{S↓c} F Q_{c} where Q_{c} : S ↓ c → 𝔻 is defined as Q_{c}(S(d) → c) = d. Recall that the diagonal functor Δ_{𝔻} : Ab → Ab^{𝔻} [16] assigns to each abelian group A the functor Δ_{𝔻}A : 𝔻 → Ab which has the value A at each d ∈ Ob 𝔻 and the value 1_{A} at each α ∈ Mor 𝔻. If f : A → B is a morphism in Ab, then Δ_{𝔻}(f) : Δ_{𝔻}A → Δ_{𝔻}B is the natural transformation which has the same value f at each object d ∈ Ob 𝔻. Since colim^{𝔻} is left adjoint to the diagonal functor Δ_{𝔻} : Ab → Ab^{𝔻}, there is a natural isomorphism colim^{𝔻} F ≅ colim^{ℂ} Lan^{S} F. If 𝔻 is discrete, then Lan^{S} F has values { ⨁_{S(d)→c} F (d)}_{c∈ ℂ}. We will consider any set E as a

discrete category and a family {S(e)}_{e∈E} as the functor S : E → ℂ. Now we define a proper class in Ab^{ℂ} such that the diagrams Lan^{S} F are relative projective for every family {F (e)}_{e∈E} of abelian groups F (e). It allows us to consider the groups H_{n}( ℂ, F) as the values of relative derived functors of the colimit.

A short exact sequence 0 → A′ →^{f′} A →^{f′′} A′′ → 0 of abelian groups splits if there exists a homomorphism ν′′ : A′′ → A such that f′′ ∘ ν′′ = 1_{A′′}. This is equivalent to the existence of ν′ : A → A′ such that ν′ ∘ f′ = 1_{A′}. We consider a proper class P in the sense of S. Mac Lane [15, Ch. XII] in the category Ab^{ℂ}. This class consists of all short exact sequences (2) of diagrams for which the exact sequences (3) split for each c ∈ Ob ℂ. The class of proper epimorphisms P_{e} consists of all η′′ for which the sequence (2) with η′ = ker(η′′) belong to P. The class of proper monomorphisms P_{m} consists of all η′ for which the sequence (2) with η′′ = coker(η′) belong to P. The diagram F ∈ Ab^{ℂ} is relative projective if the hom functor Ab^{ℂ}(F, −) : Ab^{ℂ} → Ab carries the proper epimorphisms to epimorphisms.

A natural transformation η is proper if it is equal to a composition μ ∘ ε of a proper monomorphism μ and a proper epimorphism ε.

Lemma 2.3. Let E be a set and ℂ a small category. For each map S : E → Ob ℂ and family {G(e)}_{e∈E} of abelian groups the diagram Lan^{S} G is relative projective.

Let S : Ob ℂ → ℂ be the inclusion of maximal discrete subcategory of ℂ. We denote by O = Ab^{S} : Ab^{ℂ} → Ab^{Ob ℂ} the functor of the restriction and L = Lan^{S} : Ab^{Ob ℂ} → Ab^{ℂ} the left Kan extension. Let ε : LO → Id_{Ab^{ℂ}} be the counit of the adjunction. Then for each diagram F ∈ Ab^{ℂ} we have by [23] the following exact sequence consisting of proper morphisms

0 ← F ⟵^{ε_{F}} F_{0} ⟵^{d_{1}} F_{1} ⟵^{d_{2}} ⋯ ⟵^{d_{n}} F_{n} ⟵^{d_{n+1}} ⋯

with F_{n} = (LO)^{n+1}F and d_{n} = ∑_{k=0}^{n}(−1)^{k}d_{n}^{k} where d_{n}^{k} = (LO)^{k}(ε_{(LO)^{n−k}F}). It is a

relative projective resolution of F by Lemma 2.3. The sequence 0 ← F_{0} ←^{d_{1}} F_{1} ←^{d_{2}} ⋯ is denoted by F_{∗}. The passage to colimit of F_{∗} gives a complex colim^{ℂ} F_{∗} ≅ C_{∗}( ℂ, F). Hence H_{n}(colim^{ℂ} F_{∗}) ≅ H_{n}( ℂ, F). If P_{∗} → F is another proper projective resolution, then there exists a chain morphism P_{∗} → F_{∗} which is a homotopy equivalence. The functor colim^{ℂ} : Ab^{ℂ} → Ab is additive and consequently respects homotopy equivalences. Hence the complexes colim^{ℂ} P_{∗} and colim^{ℂ} F_{∗} have the same homology groups. Thus H_{n}(colim^{ℂ} P_{∗}) ≅ H_{n}(colim^{ℂ} F_{∗}) ≅ H_{n}( ℂ, F) for all n ⩾ 0 and for each proper projective resolution P_{∗} → F. We will use this fact in the proof of Theorem 3.2.

The domain of the functors H_{n}(−, =) may be extended to a category Dg(Ab) whose objects are pairs ( ℂ, F) consisting of small categories ℂ and diagrams F : ℂ → Ab. In the category Dg(Ab) any morphism (S, η) : ( ℂ, F) → ( 𝔻, G) will be consisted of a functor S : ℂ → 𝔻 and a natural transformation η : F →

G ∘ S. The composition of morphisms ( ℂ, F) ⟶^{(S,η)} ( 𝔻, G) ⟶^{(T,σ)} ( 𝔼, H) is defined as (T ∘ S, (σ ∗ S) · η)). The identity morphism (1_{ℂ}, 1_{F}) consists of the functor 1_{ℂ} : ℂ → ℂ and the identity natural transformation.

Let ( ℂ, F) ⟶^{(S,η)} ( 𝔻, G) be a morphism in Dg(Ab). Then the natural transformation η : F → G ∘ S defines the coproduct homomorphism

⨁_{c_{0}→···→c_{n}} F (c_{0}) → ⨁_{c_{0}→···→c_{n}} G(S(c_{0})).

The universality of the canonical injections

G(S(c_{0})) ⟶^{λ_{c_{0}}} ⨁_{c_{0}→···→c_{n}} G(S(c_{0}))

and the homomorphisms

G(S(c_{0})) ⟶^{λ′_{S(c_{0})}} ⨁_{d_{0}→···→d_{n}} G(d_{0})

give rise to the homomorphisms

⨁_{c_{0}→···→c_{n}} G(S(c_{0})) ⟶ ⨁_{d_{0}→···→d_{n}} G(d_{0})

inducing a chain homomorphism. This leads to the homomorphisms

H_{n}( ℂ, F) → H_{n}( ℂ, G ∘ S) → H_{n}( 𝔻, G)

for all n ⩾ 0. The composition gives functors H_{n}(−, =) : Dg(Ab) → Ab, n ⩾ 0.

3. Interpretation of the first homology group of a category

The work [9] gave an interpretation of the first homology group of the free category generated by a directed graph. The elements of the first homology group were considered as families of “currents” which are assigned to edges and satisfy the “First Kirchhoff Law” at every vertex. Homological algebra was used for the study of abelian groups of flows. This section is devoted to an interpretation of the first homology group of a category given by a rewriting system.

We first consider the case of a free category. Let Γ be a directed graph. Suppose that F : PaΓ → Ab is a diagram of abelian groups.

Definition 3.1. A flow in Γ with coefficients in F is a family {f_{γ}}_{γ∈A(Γ)} of members f_{γ} ∈ F (dom γ) such that:

(i) the sets {γ ∈ A(Γ) : f_{γ} ≠ 0} are finite;

(ii) for each c ∈ V (Γ) the equality ∑_{c=cod(γ)} F (γ)(f_{γ}) = ∑_{c=dom(γ)} f_{γ} holds.

Flows with intensifications and flows with delays are examples of such generalized flows [9]. It is clear that the flows in Γ with coefficients in F form a subgroup of the 1-chain group ⨁_{γ∈A(Γ)} F (dom(γ)). Denote the subgroup of all flows by Φ(Γ, F).

The following assertion was proved in [9]

Proposition 3.1. For every diagram F : PaΓ → Ab there is an isomorphism Φ(Γ, F) ≅ colim_{1}^{PaΓ} F.

We now introduce the notion of an internal flow. Denote the values in_{i}(a) of the canonical homomorphisms A_{i} → ⨁_{i∈I} A_{i}, of a ∈ A_{i}, by a[i]. Every member of

the coproduct admits a shape ∑_{i∈I} a_{i}[i] where a_{i} ∈ A_{i} with the condition a_{i} ≠ 0 for

only a finite set of i ∈ I. Let Γ be a directed graph and R some set of parallel pairs in the path category PaΓ. Let ℂ be a small category given by a rewriting system (Γ, R) and π : PaΓ → ℂ the canonical projection. Let F : ℂ → Ab be a diagram of abelian groups. Given paths α = α_{m} ⋯ α_{1} and β = β_{n} ⋯ β_{1} with r = (α, β) ∈ R

[figure: ⋯; ⋯; f; −f; −F (β_{1})f; F (α_{1})f; F (α_{m−1} ⋯ α_{1})f; −F (β_{n−1} ⋯ β_{1})f; α_{1}; α_{2}; β_{1}; β_{2}; β_{n}; α_{m}]

Figure 2: The internal flow d_{1}(f[r])

we denote by dom r their common domain and cod r the codomain. For any path w = γ_{k} ⋯ γ_{1} of edges γ_{i} ∈ A(Γ) and a member f ∈ F (dom γ_{1}), k > 0 we denote δf[γ_{k} ⋯ γ_{1}] = f[γ_{1}] + F (γ_{1})(f)[γ_{2}] + ⋯ + F (γ_{k−1} ⋯ γ_{1})(f)[γ_{k}]. Let δf[w] = 0 if k = 0 (for the empty path). Then for each member f ∈ F (π(dom(r))) there exists a flow in Γ with coefficients in F ∘ π which equals the difference of the 1-chains δf[α] − δf[β]. The values of this flow are pictured in fig. 2.

Denote the flow by d_{1}(f[r]).

A flow φ ∈ Φ(Γ, F ∘ π) is called internal with respect to R if there are r_{i} ∈ R,

f_{i} ∈ F ∘ π(dom(r_{i})), 1 ⩽ i ⩽ k, such that φ = ∑_{i=1}^{k} d_{1}(f_{i}[r_{i}]). Denote by I(Γ, R, F)

the abelian group of all flows internal with respect to R.

Consider the sequence of homomorphisms

⨁_{r∈R} F (dom r) →^{d_{1}} ⨁_{γ∈A(Γ)} F (dom γ) →^{d_{0}} ⨁_{v∈Ob ℂ} F (v) → 0,  (5)

where d_{0}(f[γ]) = f[dom γ] − F (γ)f[cod γ]. It follows from the equality

d_{0} ∑ f_{γ}[γ] = ∑_{v∈V (Γ)} ( ∑_{v=dom γ} f_{γ} − ∑_{v=cod γ} F (γ)f_{γ} ) [v],

that Φ(Γ, F ∘ π) = Ker d_{0}. Since d_{1}(f[r]) is a flow, we have d_{0}(d_{1}(f[r])) = 0. Therefore, the sequence (5) is a complex. The colimit of F is isomorphic to the cokernel of d_{0}. Hence the 0-th homology group ⨁_{v∈Ob ℂ} F (v)/ Im(d_{0}) of (5) is isomorphic to

colim^{ℂ} F.

Theorem 3.2. Let ℂ be a small category and F : ℂ → Ab a functor. For each presentation (Γ, R) of ℂ there is an isomorphism

Φ(Γ, F ∘ π)/I(Γ, R, F) ≅ colim_{1}^{ℂ} F

where π : PaΓ → ℂ is the canonical projection.

Example 3.2. Let Γ be the graph

a \underrightarrow{β} ; \overleftarrow{α} b ,

with V (Γ) = {a, b}, A(Γ) = {α, β}, and R = (1_{a}, αβ). The presentation (Γ, R) defines the category ℂ in which α ∘ β = 1_{a}. For any diagram F : ℂ → Ab we have F (α) ∘ F (β) = 1_{F (a)}. Every flow in Γ with coefficient in F consists of two members f_{α} ∈ F (b), f_{β} ∈ F (a) such that F (α)(f_{α}) = f_{β} and F (β)(f_{β}) = f_{α}. It follows from the second equality that F (α)∘F (β)(f_{β}) = F (α)(f_{α}) and, consequently, F (α)(f_{α}) = f_{β}. Hence the first equality is unnecessary. Therefore Φ(Γ, F) ≅ F (b) and each flow is equal to f_{β}[β] + F (β)f_{β}[α]. Internal flows consist of sums of lows f[β] + F (β)f[α]. Thus every flow is internal and H_{1}( ℂ, F) = 0.

Corollary 3.3. The quotient group Φ(Γ, F ∘ π)/I(Γ, R, F) does not depend on a presentation (Γ, R) of ℂ.

For the proof of the theorem, we will use the following lemma which is a direct corollary of [18, Theorem 28.1].

Let ℂ be a small category given by a presentation (Γ, R) and π : PaΓ → ℂ the canonical projection. We can let Ob ℂ = V (Γ), π(v) = v, for all vertices v ∈ V (Γ). For c ∈ Ob ℂ, the objects of the category π↓c may be regarded as pairs (v, x) with v ∈ V (Γ) and x ∈ ℂ(π(v), c). Consequently Ob(π↓c) = Ob( ℂ↓c). Morphisms of π↓c may be regarded as triples (α : a → b, x, y) which consist of α ∈ Mor(PaΓ), x ∈ ℂ(a, c), y ∈ ℂ(b, c) satisfying y ∘ π(α) = x. In these triples, x depends on α and y, hence morphisms in π↓c may be described as pairs (α ∈ ℂ(a, b), y ∈ ℂ(b, c)). Similarly morphisms of ℂ↓c may be given as pairs (α ∈ ℂ(a, b), x ∈ ℂ(b, c). Morphisms (γ, x) of π↓c form the arrows of a directed graph. We will denote this graph by Γ↓c. Let R↓c consisting of pairs ((α, x), (β, x)) in π↓c such that (α, β) ∈ R. Define a forgetful functor U_{c} : π↓c → ℂ↓c by U_{c}(v, x) = (v, x) and U_{c}(α, y) = (π(α), y). Then (Γ↓c, R↓c) is the presentation of ℂ↓c with the canonical projection U_{c}.

Let Q_{c} : ℂ↓c → ℂ be the functor assigning to every object (a, x) the object a ∈ ℂ and to every morphism (f : a → b, y) the morphism f. For each diagram F : ℂ → Ab, one can consider the diagram F Q_{c}.

We replace in the sequence (5) the letters F, R, Γ, ℂ by F Q_{c}, R↓c, Γ↓c, ℂ↓c respectively. After the augmentation by coker d_{0} = colim^{ℂ↓c} F Q_{c} = F (c), this sequence may be transformed to the sequence, natural in c ∈ ℂ,

⨁_{cod(r)→c} F (dom r) ⟶^{d_{1}} ⨁_{cod γ→c} F (dom γ) ⟶^{d_{0}} ⨁_{v→c} F (v) ⟶^{d_{−1}} F (c) ⟶ 0 (6)

Lemma 3.4. For each c ∈ ℂ the sequence (6) of abelian groups is exact.

Proof. It is enough to show that for each object c ∈ ℂ, there are homomorphisms

⨁_{cod(r)→c} F (dom r) ⟵^{θ_{1}} ⨁_{cod γ→c} F (dom γ) ⟵^{θ_{0}} Im d_{0},

such that θ_{0}d_{0} + d_{1}θ_{1} = 1. Denote for a path w = γ_{n} ⋯ γ_{1} and morphism x : cod(w) → c

δ(f[γ_{n} ⋯ γ_{1}, x]) = f[γ_{1}, xγ_{n} ⋯ γ_{2}] + F (γ_{1})(f)[γ_{2}, xγ_{n} ⋯ γ_{3}] + ⋯ ⋯ + F (γ_{n−1} ⋯ γ_{1})(f)[γ_{n}, x].

Then d_{1}(f[r, x]) = δ(f[α, x]) − δ(f[β, x]), for paths α and β which form r = (α, β).

To construct θ_{0}, for every α ∈ Mor ℂ we choose a path γ_{n} ⋯ γ_{1} such that π(γ_{n} ⋯ γ_{1}) = α. Denote it by τ(α). Let for τ(x) = γ_{n} ⋯ γ_{1},

θ_{0}(f[v, x]) = δ(f[τ(x), 1_{c}]) = f[γ_{1}, γ_{n} ⋯ γ_{2}]+ F (γ_{1})(f)[γ_{2}, γ_{n} ⋯ γ_{3}] + ⋯ + F (γ_{n−1} ⋯ γ_{1})(f)[γ_{n}, 1_{c}].

Then define a homomorphism θ_{1} : ⨁_{cod γ→c} F (dom γ) → ⨁_{cod(r)→c} F (dom r) as follows.

For any γ ∈ A(Γ) and x ∈ ℂ(cod γ, c) we have τ(x) · γ = τ(xγ). This implies that there exists a 2-path from τ(x) · γ to τ(xγ) given by a sequence (y_{i}, α^{i}, β^{i}, z_{i}), with r_{i} = (α^{i}, β^{i}) ∈ R consisting of paths α^{i} = α_{m}^{i} ⋯ α_{1}^{i} and β^{i} = β_{n}^{i} ⋯ β_{1}^{i}. Let

θ_{1}(f[γ, x]) = ∑_{i=1}^{k} F (y_{i})(f)[r_{i}, z_{i}]. It is proved in [18] that θ_{0}d_{0} + d_{1}θ_{1} = 1. Then for

z ∈ ⨁_{cod γ→c} F (dom γ) satisfying d_{0}z = 0 we have (θ_{0}d_{0}+d_{1}θ_{1})z = z and consequently

z = d_{1}(θ_{1}z). Hence Ker d_{0} = Im d_{1}. It follows from d_{1}θ_{1} = (1 − θ_{0}d_{0})d_{1} = d_{1}, that d_{1}θ_{1}|_{Im d_{1}} = 1_{Im d_{1}}. Thus the sequence consists of proper natural transformations. □

Proof of Theorem 3.2. Recall that for any set E and a family of abelian groups G = {G(e)}_{e∈E} and a map S : E → Ob ℂ the values of the left Kan extension of G are equal to Lan^{S} G(c) = ⨁_{S(e)→c} G(e). In this case we will have an isomorphism

colim^{ℂ}{ ⨁_{S(d)→c} G(d)} ≅ ⨁_{d∈ 𝔻} G(d).

The substitutions 𝔻 = R, G = F ∘ dom, S = cod : R → ℂ lead us to

colim^{ℂ}{ ⨁_{cod(r)→c} F (dom(r))} ≅ ⨁_{r∈R} F (dom(r)).

Replacing 𝔻 = A(Γ), G = F ∘ dom, S = cod : A(Γ) → ℂ we get

colim^{ℂ}{ ⨁_{cod γ→c} F (dom γ)} ≅ ⨁_{γ∈A(Γ)} F (dom γ).

If we replace the inclusion Ob ℂ ⊆ ℂ by S and substitute 𝔻 = V (Γ), G = F |_{Ob ℂ} , then we obtain

colim^{ℂ}{⨁_{v→c} F (v)} ≅ ⨁_{v∈V (Γ)} F (v).

Therefore the colimit of the sequence (6) gives a complex of abelian groups and homomorphisms

⨁_{r∈R} F (dom r) → ⨁_{γ∈A(Γ)} F (dom γ) → ⨁_{v∈Ob ℂ} F (v) → 0 .

The commutativity of the following diagram follows immediately:

⨁_{r∈R} F (dom r) ⟶^{d_{1}}  ⨁_{γ∈A(Γ)} F (dom γ) ⟶^{d_{0}}  ⨁_{v∈Ob ℂ} F (v)
↑ λ′_{c}  ↑ λ_{c}  ↑ λ′′_{c}
⨁_{cod r→c} F (dom r) ⟶^{d_{1}}  ⨁_{cod γ→c} F (dom γ) ⟶^{d_{0}}  ⨁_{v→c} F (v)

(7)

where {λ_{c}}, {λ′_{c}}, {λ′′_{c}} are the colimit cones. We obtain a complex with homology groups

H_{0} = colim^{ℂ} F, H_{1} = Φ(Γ, F ∘ π)/I(Γ, R, F).

Since the morphisms of the upper string in (7) making these diagrams commutative are unique, the upper string complex is the colimit of the relatively projective resolution consisting of proper natural transformations. Therefore by [23], its homology groups are isomorphic to colim_{n}^{ℂ} F, n = 0, 1. □

Corollary 3.5. If a presentation (Γ, R) of ℂ has no nondegenerate closed 2-paths, then H_{n}( ℂ, F) = 0, for n ⩾ 3. In this case H_{2}( ℂ, F) is isomorphic to the kernel of the homomorphism d_{1} : ⨁_{r∈R} F (dom r) → ⨁_{γ∈A(Γ)} F (dom γ) which acts as d_{1}f[r] =

δf[α] − δf[β].

Proof. It follows from [18, Remark 1, p. 108] that if all closed 2-paths (y, s, t, z) are degenerate, then the kernel of

d_{1} : ⨁_{cod(r)→c} F (dom r) → ⨁_{cod γ→c} F (dom γ)

is zero. Hence if Ω(R) is trivial, then we obtain the exact sequence

0 → ⨁_{cod(r)→c} F (dom r) ⟶^{d_{1}} ⨁_{cod γ→c} F (dom γ) ⟶^{d_{0}} ⨁_{v→c} F (v) ⟶^{d_{−1}} F (c) → 0

which is a proper projective resolution of F in Ab^{ℂ}. The passage to the colimit by c ∈ ℂ gives the complex which homologies are equal to H_{n}( ℂ, F). Thus H_{n}( ℂ, F) = 0 for n ⩾ 3 and H_{2}( ℂ, F) is isomorphic to the kernel of d_{1} : ⨁_{r∈R} F (dom r) →

⨁_{γ∈A(Γ)} F (dom γ). □

Smith normal form and calculating the homology groups. Let G′ →^{α} G →^{β} G′′ be homomorphisms of abelian groups such that β ∘ α = 0. Then we can consider the homology group Ker(β)/ Im(α). Let us describe a method of calculation for this homology group when G′, G, and G′′ are finitely generated free abelian groups.

Proposition 3.6. [20, Theorem III.4(43)] Let

A = (\begin{matrix}a_{11} & a_{12} & ⋯ & a_{1n} \\ a_{21} & a_{22} & ⋯ & a_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{m1} & a_{m2} & ⋯ & a_{mn} \end{matrix})

be a matrix with integer entries a_{ij} ∈ ℤ. Then there is an m × m matrix T and an n × n matrix S with integer entries such that:

(i) det(T) = ±1, det(S) = ±1;

(ii) A = T ∘ D(A) ∘ S for a natural number k ⩾ 0 and m × n matrix

D(A) = (\begin{matrix}d_{1} & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & d_{2} & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & ⋯ & d_{k} & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \end{matrix})

all entries of which are equal to 0 except the diagonal numbers d_{1} ⩽ d_{2} ⩽ ⋯ ⩽ d_{k} which satisfy that d_{i} divides d_{i+1} for all 1 ⩽ i ⩽ k − 1.

The matrix D(A) is said to be a Smith normal form of A. This form is used for the computation of the homology groups of simplicial complexes in [24]. We refer the reader to [6], where an algorithm is presented for computing the Smith normal form of an integer matrix, which performs well in practice. There are packages such as GAP for the computation of the Smith normal form.

Proposition 3.7. Let a homomorphism α : ℤ^{n} → ℤ^{m} be given by a m × n matrix A and β : ℤ^{m} → ℤ^{p} by p × m matrix B. Suppose the sequence ℤ^{n} →^{α} ℤ^{m} →^{β} ℤ^{p} satisfies to β ∘α = 0. If d_{1}, d_{2}, ⋯, d_{k} are the nonzero diagonal entries of the Smith normal form D(A), then

Ker β/ Im α ≅ ℤ/d_{1}ℤ × ℤ/d_{2}ℤ × ⋯ × ℤ/d_{k}ℤ × ℤ^{m−k−b}  (8)

where b is the rank of the matrix B and may be computed as the number of nonzero entries of D(B).

Proof. It follows from Proposition 3.7 that one has the commutative diagram

ℤ^{n} ⟶^{α} ℤ^{m}
↑ σ′  ↑ τ
ℤ^{n} ⟶^{δ} ℤ^{m}

with isomorphisms σ′ and τ where δ is given by the matrix D(A) which is the Smith normal form of A. It follows that ℤ^{m}/ Im α ≅ ℤ^{m}/ Im δ. Consequently

ℤ^{m}/ Im α ≅ ℤ/d_{1}ℤ × ℤ/d_{2}ℤ × ⋯ × ℤ/d_{k}ℤ × ℤ^{m−k}.

Similarly, Im α ≅ Im δ.

The inclusion Ker β ⊆ ℤ^{m} induces the inclusion Ker β/ Im α ⊆ ℤ^{m}/ Im α which gives the short exact sequence

0 → Ker β/ Im α → ℤ^{m}/ Im α → ℤ^{m}/ Ker β → 0.

It follows from ℤ^{m}/ Ker β ≅ Im β that ℤ^{m}/ Ker β is free because it is isomorphic to a subgroup of ℤ^{p}. Its rank is equal to b. Consequently the short exact sequence is split, and there exists the isomorphism ℤ^{m}/ Im α ≅ (Ker β/ Im α) ⨁ ℤ^{b}. Thus ℤ^{b} is a direct summand in ℤ^{m−k} ⊆ ℤ^{m}/ Im α. Taking the quotient group by ℤ^{b} we obtain the isomorphism (8). □

We conclude that for calculating the homology group Ker β/ Im α it is enough to find the Smith normal form of matrices defining homomorphisms α and β. Then we will know the numbers d_{1}, ⋯, d_{k}, b, which determine the homology group.

We will apply the methods given above for the interpretation and the calculation of the homology groups of asynchronous transition systems. Now we supply the necessary definitions.

4. Asynchronous transition systems

We study models of computations to be executed on a multi-processor machine. Such computations can be either synchronous or asynchronous. In synchronous computations there is a global clock, and each processor executes the instructions synchronously.

We consider computations in which there is no global clock and communications are made through channels. They are called asynchronous computations. An asynchronous computation is usually called a distributed computing while a synchronous computation is called a parallel computing. We suppose that processors have data communications by means of buffers in the common memory.

Petri nets. In the case when communications yield by means of buffers in the common memory, the behaviour of computations is well described by a mathematical model which can be defined as follows:

Definition 4.1. A Petri net N = (T, P, F, M_{0}) consists of two disjoint sets T, P and two functions F : (P × T) ∪ (T × P) → {0, 1}, M_{0} : P → ℕ = {0, 1, 2, ⋯ }. Members of T are called transitions, of P places. The function M_{0} is said to be an initial marking. The function F determines a structure of a directed bipartite graph with the set P ∪ T of vertices in which the set of arrows consists of pairs (a, b) ∈ (P × T) ∪ (T × P) such that F (a, b) = 1.

A marking is a function M : P → ℕ. Transitions act on the set of all markings. A marking M may be changed if there exists a transition t ∈ T such that F (p, t) ⩽ M(p) for all p ∈ P. A new marking M′ is defined by its values M′(p) = M(p) − F (p, t)+F (t, p). In this case we will say that the transition t ∈ T happens and write M →^{t} M′. A Petri net behaviour is a sequence of markings M_{0} →^{t_{1}} M_{1} →^{t_{2}} M_{2} →^{t_{3}} · · ·.

Places are pictured as circles and transitions as rectangles. If F (a, b) = 1, then a and b are connected by an arrow. For each p ∈ P the corresponding circle contains

[figure: t_{1}; t_{1}; t_{1}; t_{1}; t_{0}; t_{0}; t_{0}; t_{0}; t_{2}; t_{2}; t_{2}; t_{2}; p_{1}; p_{1}; p_{1}; p_{1}; p_{0}; p_{0}; p_{0}; p_{0}; p_{2}; p_{2}; p_{2}; p_{2}; p_{3}; p_{3}; p_{3}; p_{3}; p_{4}; p_{4}; p_{4}; p_{4}; p_{5}; p_{5}; p_{5}; p_{5}]

Figure 3: The behaviour of a Petri net.

M(p) points. A transition t may happen if every arrow going into t has at least one point in its domain place. When t happens, a point is deleted from the domain of each arrow going into t and then a point is added to the codomain of each arrow going out of t.

Example 4.2. We consider a possible behaviour of the computing system which contains the operator sequence:

t_{0} : s := 0; t_{1} : s := s + a; t_{2} : s := s + b.

The Petri net (Fig.3) consists of T = {t_{0}, t_{1}, t_{2}}, P = {p_{0}, p_{1}, p_{2}, p_{3}, p_{4}, p_{5}} with the characteristic function F corresponding to the subset of pairs (p_{0}, t_{0}), (p_{1}, t_{1}), (p_{2}, t_{2}), (p_{5}, t_{1}), (p_{5}, t_{2}), (t_{0}, p_{5}), (t_{1}, p_{3}), (t_{1}, p_{5}), (t_{2}, p_{4}), (t_{2}, p_{5}) and the initial marking M_{0}(p_{0}) = M_{0}(p_{1}) = M_{0}(p_{2}) = 1, M_{0}(p_{3}) = M_{0}(p_{4}) = M_{0}(p_{5}) = 0.

The transitions happen in the order M_{0} →^{t_{0}} M_{1} →^{t_{1}} M_{2} →^{t_{2}} M_{3}. At first t_{0} happens, it is deleted the point from p_{0} and is added the point to the place p_{5}. Then it may happen that either t_{1} or t_{2}. We have taken t_{1}. When t_{1} happens, they are deleted points from p_{1} and p_{5}; and then they are added points to p_{3} and p_{5}. Then it happens t_{2}, similarly. In this example the program is executed by processes t_{0}, t_{1}, t_{2}. The communications are made through s.

CE nets. In the case of communications by buffers each of which has the 1 member, the values of the marking M(p) are not greater than 1. Such Petri nets are called CE nets. For a CE net any marking M : P → {0, 1} may be regarded as the characteristic function of the subset M^{−1}(1) ⊆ P. This subset is called a state of CE net. The subset corresponding to the initial marking will be called the initial state. A transition t may happen if for all p ∈ P the following two conditions hold:

(i) F (p, t) ⩽ M(p),

(ii) M′(p) = M(p) − F (p, t) + F (t, p) ⩽ 1.

Transitions of CE nets are called events and places are called conditions. They are denoted B = P, E = T. Markings M : B → {0, 1} are regarded as subsets M ⊆ B and are called states.

Let N = (E, B, F, M_{0}) be a CE net. For e ∈ E put

pre(e) = {b ∈ B : F (b, e) = 1}, post(e) = {b ∈ B : F (e, b) = 1}.

We have the directed graph

E \underrightarrow{pre} ; \overrightarrow{post} 2^{B},

where 2^{B} is the set of all subsets in B. Conversely, every collection of sets E, B and functions pre, post : E → 2^{B} and a subset M_{0} ⊆ B gives a CE net (E, B, F, M_{0}) in which the function F : (E × B) ∪ (B × E) → {0, 1} has values

F (x, y) = \begin{cases}1, & if x ∈ pre(y) or y ∈ post(x), \\ 0, & otherwise. \end{cases}

It allows us to consider a CE net as a collection

N = (B, M_{0}, E, pre, post),

which consists of sets B and E, a subset M_{0} ⊆ B and maps E \underrightarrow{pre} ; \overrightarrow{post} 2^{B}.

Morphisms of CE nets are defined as some morphisms of corresponding directed graphs.

To give the definition we need the category of sets and partial functions [26]. A partial function f : A ⇀ B is a pair consisting of a subset dom f ⊆ A and a map f : dom f → B. The composition is defined in the obvious way. We assign to every set E the set E_{∗} = E ∪ {⋆} obtained by the addition of an “infinitely distant” point ⋆ which does not belong to E. We assign to every partial function E ⇀^{f} E′ the (based) map f_{∗} : E_{∗} → E′_{∗} with values

f_{∗}(e) = \begin{cases}f(e), & if e ∈ dom f, \\ ⋆, & otherwise. \end{cases}

This defines the isomorphism of the category of sets and partial function with the category Set_{∗} whose objects are pointed sets (often called “based” sets) and morphisms are based maps in the sense of [16]. Thus we can consider a partial function as the corresponding map which preserves base points.

For a CE net (B, M_{0}, E, pre, post) we extend the maps pre and post to E_{∗} by pre(⋆) = post(⋆) = ∅.

Definition 4.3. For arbitrary CE nets

N = (B, M_{0}, E, pre, post), N′ = (B′, M′_{0}, E′, pre′, post′)

a morphism (β, η) : N → N′ is a pair consisting of a based map η : E_{∗} → E′_{∗} and a partial function β : B′ ⇀ B such that

(i) the diagrams

\begin{matrix}E_{∗} & ⟶^{pre} & 2^{B} \\ ↓ η & & ↓ β^{−1} \\ E′_{∗} & ⟶^{pre′} & 2^{B′} \end{matrix}  \begin{matrix}E_{∗} & ⟶^{post} & 2^{B} \\ ↓ η & & ↓ β^{−1} \\ E′_{∗} & ⟶^{post′} & 2^{B′} \end{matrix}

are commutative where β^{−1}(M) = {b′ ∈ B′ : (∃b ∈ M)β(b′) = b}; (ii) β^{−1}(M_{0}) = M′_{0}.

If (pre(e_{1}) ∪ post(e_{1})) ∩ (pre(e_{2}) ∪ post(e_{2})) = ∅, then e_{1} and e_{2} are said to be independent.

Lemma 4.1. [26] Let N = (B, M_{0}, E, pre, post), N′ = (B′, M′_{0}, E′, pre′, post′) be CE nets and (β, η) : N → N′ a morphism of CE nets. Then

(i) if a transition M →^{e} M′ happens in N, then β^{−1}(M) →^{η(e)} β^{−1}(M′) happens in N′;

(ii) if e_{1} and e_{2} are independent, then η(e_{1}) and η(e_{2}) are independent in N′.

Proof. The assertion follows from the fact that β^{−1} preserves the difference and intersection of sets.

Asynchronous transition systems. Consider an arbitrary set S of computing system states with a set of instructions E which act on S. Some of the instructions can act at the same time.

Definition 4.4. [26] An asynchronous transition system

A = (S, s_{0}, E, I, T ran)

consists of sets S and E, a member s_{0} ∈ S, a subset T ran ⊆ S × E × S, and an irreflexive symmetric relation I ⊆ E × E for which

(i) for every e ∈ E there are s, s′ ∈ S such that (s, e, s′) ∈ T ran;

(ii) if (s, e, s′) ∈ T ran and (s, e, s′′) ∈ T ran, then s′ = s′′;

(iii) for every pair (e_{1}, e_{2}) ∈ I and triples (s, e_{1}, s_{1}) ∈ T ran, (s_{1}, e_{2}, u) ∈ T ran there exists s_{2} ∈ S such that (s, e_{2}, s_{2}) ∈ T ran, (s_{2}, e_{1}, u) ∈ T ran.

Members of S are called states, members of T ran are transitions, s_{0} ∈ S is an initial state, I is an independence relation.

The condition (iii) of Definition 4.4 may be illustrated by the diagram:

[figure: s; e_{1}; e_{2}; e_{1}; e_{2}; s_{1}; s_{2}; u]

The following asynchronous transition system corresponds to the well known reader and writer problem and it is considered in computer architecture courses (see [10]).

Example 4.5. [10] Processes are loaded to execute in accidental times. They can read data from a common page in the memory. There are processes which have access for writing data in the common page. They are called writers. The other processes are called readers. At any time, only one writer can have access to the common page. Readers have no access if there is a writer which is working with the common page. Writers have the following advantage: if a writer is ready to write a data, then new readers are not allowed to access the common page. There is a queue of writers.

This problem can be modeled as programs for the readers and writers. By executing these programs, we obtain a sequence of states which may be described as the states of the following asynchronous transition system. Every state of the system is a pair (r, w), where r is the number of readers working with the common page and w the number of writers which are ready to write in the page. If there are no readers, then the first writer works with the common page. The initial state is s_{0} = (0, 0).

(0, 0) \underleftarrow{d} ; \overrightarrow{c} (0, 1) \underleftarrow{d} ; \overrightarrow{c} (0, 2) \underleftarrow{d} ; \overrightarrow{c} (0, 3) \underleftarrow{d} ; \overrightarrow{c} ⋯
a ↓ ↑b ↑ b ↑ b ↑ b
(1, 0) \overrightarrow{c} (1, 1) \overrightarrow{c} (1, 2) \overrightarrow{c} (1, 3) \overrightarrow{c} ⋯
a ↓ ↑b ↑ b ↑ b ↑ b
(2, 0) \overrightarrow{c} (2, 1) \overrightarrow{c} (2, 2) \overrightarrow{c} (2, 3) \overrightarrow{c} ⋯
a ↓ ↑b  ↑ b  ↑ b  ↑ b
⋯  ⋯  ⋯  ⋯

The letters denote the events:

′a′ a reader got the access to the common page; ′b′ a reader freed the access; ′c′ a new writer appeared; ′d′ a writer finished.

If w > 0, then a new reader cannot get the access. If r > 0, then there are no writers working with the page. In this case the event d cannot occur. If r > 0, then the event b can occur that leads to the subtraction of 1 from r. The event c can occur in an arbitrary time, it adds 1 to w. The event a can occur when w = 0. The event d can come if r = 0 and w > 0. It is supposed that for w writers in the queue the first writer gets the access after the exits of all readers. It is clear that b and c are independent. Thus I = {(b, c), (c, b)}.

The following asynchronous transition system is obtained

( ℕ × ℕ, (0, 0), {a, b, c, d}, {(b, c), (c, b)}, T ran),

where T ran = {((i, 0), a, (i + 1, 0)) : i ∈ ℕ} ∪ {((0, j + 1), d, (0, j)) : j ∈ ℕ} ∪ {((i + 1, j), b, (i, j)) : i ∈ ℕ, j ∈ ℕ} ∪ {((i, j), c, (i, j + 1)) : i ∈ ℕ, j ∈ ℕ}.

The category of asynchronous transition system. We will prove that asynchronous transition systems may be regarded as pointed sets over partially commutative monoids.

Definition 4.6. A right pointed set over a monoid is a triple (M, ·, X) of a monoid M and a based set X together with a map · : X × M → X such that the following three conditions hold

(i) ⋆ · μ = ⋆, for all μ ∈ M;

(ii) (x · μ_{1}) · μ_{2} = x · (μ_{1}μ_{2}), for all x ∈ X and μ_{1}, μ_{2} ∈ M;

(iii) x · 1 = x, for all x ∈ X.

Here 1 is the identity element of the monoid. The symbol ′·′ is omitted usually. So a (right) pointed set over a monoid is denoted by (M, X).

A morphism of pointed sets over monoids (η, σ) : (M, X) → (M′, X′) is a pair consisting of a monoid homomorphism η : M → M′ and based map σ : X → X′ such that σ(x · μ) = σ(x) · η(μ), for all x ∈ X, μ ∈ M.

Let (S, s_{0}, E, I, T ran) be an asynchronous transition system and let M(E, I) be a monoid given by rewriting system (E, Î), where Î is an antisymmetric and irreflexive relation consisting of pairs (ab, ba) with (a, b) ∈ I. We will suppose that for every (a, b) ∈ I either (ab, ba) or (ba, ab) belongs to Î. By the condition (ii) of Definition 4.4, for any e ∈ E, there is a map S_{∗} → S_{∗} which is not equal to the zero based map by the condition (i) of Definition 4.4. Let us denote it by \overline{S}(e) : S_{∗} → S_{∗}. The values \overline{S}(e)(s) are denoted by s · e, for s ∈ S_{∗}. According to (iii) of Definition 4.4 we have (s · a) · b = (s · b) · a, for all (a, b) ∈ I. We obtain the map \overline{S} : E → Set_{∗}(S_{∗}, S_{∗}) which determines the unique monoid homomorphism S̃ : E^{∗} → Set_{∗}(S_{∗}, S_{∗}). Since S̃(ab) = S̃(a)S̃(b) = S̃(b)S̃(a) = S̃(ba), there exists a unique extension S̃ : M(E, I) → Set_{∗}(S_{∗}, S_{∗}) of the map E → Set_{∗}(S_{∗}, S_{∗}) which gives a structure of right pointed set over M(E, I).

If we return to the asynchronous transition system for the reader and writer problem, then we obtain the right pointed set over M(E, I) where S_{∗} = ℕ× ℕ∪{⋆} and the presentation (E, Î) = ({a, b, c, d} : {(bc, cb)}) of M(E, I) with the action

(m, 0) · a = (m + 1, 0), (m + 1, n) · b = (m, n),
(m, n) · c = (m, n + 1), (0, n + 1) · d = (0, n), ∀m ∈ ℕ, n ∈ ℕ

We let (m, n) · e = ⋆ for all the rest of (m, n) and e ∈ {a, b, c, d}.

Let A be a category whose objects are asynchronous transition systems. A morphism of A

(η, σ) : (S, s_{0}, E, I, T ran) → (S′, s′_{0}, E′, I′, T ran′)

consists of a map σ : S → S′ and a partial function η : E ⇀ E′ for which σ(s_{0}) = s′_{0} and the following conditions hold:

(i) (s, a, t) ∈ T ran ⇒ (σ(s), η(a), σ(t)) ∈ T ran′, if η(a) is defined and otherwise σ(s) = σ(t);

(ii) if (e_{1}, e_{2}) ∈ I and η(e_{1}), η(e_{2}) are both defined, then (η(e_{1}), η(e_{2})) ∈ I′.

Lemma 4.2. [11] Consider the map assigning to every asynchronous transition system

(S, s_{0}, E, I, T ran)

the right pointed set (M(E, I), S_{∗}) with the action s · μ = S̃(μ)(s) for μ ∈ M(E, I) and s ∈ S_{∗}. This map may be extended to a functor from the category of asynchronous transition systems into the category of right pointed sets over partially commutative monoids.

Proof. Let

(σ, η) : (S, s_{0}, E, I, T ran) → (S′, s′_{0}, E′, I′, T ran′)

be a morphism of asynchronous transition systems. Since η : E_{∗} → E′_{∗} carries interchangeable elements to interchangeable, the homomorphism η^{∗} : E^{∗} → E^{′∗} induces the homomorphism of the quotient monoids M(E, I) → M(E′, I′). Using the implication

(s, a, t) ∈ T ran ⇒ (σ(s), η(a), σ(t)) ∈ T ran′ ∪ {(s′, ⋆, s′) : s′ ∈ S′}

we get σ(s)·η(a) = σ(s·a). Consequently any morphism of asynchronous transition systems is transformed to a morphism of right pointed sets over monoids. □

Petri nets as asynchronous transition systems. Let N be the category of CE nets and A the category of asynchronous transition systems. Following [21] we define a functor U : N → A which assign to N = (B, M_{0}, E, pre, post) the system U(N) = (S, s_{0}, E, I, T ran) where S = 2^{B}, s_{0} = M_{0}, I = {(e_{1}, e_{2}) ∈ E × E :

(pre(e_{1}) ∪ post(e_{1})) ∩ (pre(e_{2}) ∪ post(e_{2})) = ∅}, T ran = {(M, e, M′) : M →^{e} M′}.

For a morphism of CE nets (β, η) : N → N′ we let U(β, η) = (β^{−1}, η). It is well known that the functor U : N → A has a left adjoint [21].

5. Homology groups of asynchronous transition systems

For every monoid M and right pointed set (M, X) denote by K_{∗}(M, X) a category whose objects are x ∈ X and morphisms x → y are triples (x, μ, y), with μ ∈ M, satisfying to x · μ = y. If x · μ_{1} = y and y · μ_{2} = z, then x · (μ_{1}μ_{2}) = z. We conclude that the composition (y, μ_{2}, z) ∘ (x, μ_{1}, y) must be defined by (x, μ_{1}μ_{2}, z)). The identity 1_{x} : x → x equals (x, 1, x) where 1 is the identity of the monoid.

Let K(M, X) ⊆ K_{∗}(M, X) denote the full subcategory consisting of all objects x ≠ ⋆.

Homology groups of a state category. Recall that E^{∗} is the monoid of all words over an alphabet E including the empty word 1.

Definition 5.1. Let T = (S, s_{0}, E, I, T ran) be an asynchronous transition system. Let R(I) ⊆ E^{∗} × E^{∗} denote an antisymmetric and irreflexive relation consisting of pairs (e_{1}e_{2}, e_{2}e_{1}) such that (e_{1}, e_{2}) ∈ I. Consider a right pointed monoid set (M(E, I), S_{∗}), over the monoid M(E, I) which is presented by (E, R(I)) and acts on S_{∗} = S ∪ {⋆} as follows:

s · e = \begin{cases}t, & if (s, e, t) ∈ T ran, \\ ⋆, & if there are no t ∈ S such that (s, e, t) ∈ T ran. \end{cases}

An augmented graph of states of T is the directed graph with the set of vertices S_{∗} and set of arrows s →^{e} s′, for e ∈ E, s ∈ S_{∗}, s′ ∈ S_{∗} satisfying to s · e = s′. Deleting from the augmented graph of states the vertex ⋆ and all arrows for which the vertex ⋆ is the domain or the codomain we obtain a graph of states of T. The category K(T) = K(M(E, I), S_{∗}) is called the category of states, K_{∗}(T) = K_{∗}(M(E, I), S_{∗}) is the augmented category of states of T.

Example 5.2. Consider the asynchronous transition system

T = (S, s_{0}, E, I, T ran)

[figure: s_{0}; b; a; b; a; s_{2}; s_{1}; s_{3}; s_{0}; b; a; b; a; s_{2}; s_{1}; s_{3}; a; b; a; b; ⋆; b; a]

Figure 4: The graph and augmented graph of states

consisting of S = {s_{0}, s_{1}, s_{2}, s_{3}}, E = {a, b}, I = {(a, b), (b, a)}, and

T ran = {(s_{0}, a, s_{1}), (s_{0}, b, s_{2}), (s_{1}, b, s_{3}), (s_{2}, a, s_{3})}.

In Fig. 4 there are pictured two graphs which give presentations of the category of states and augmented category of states.

Let T = (S, s_{0}, E, I, T ran), T′ = (S′, s′_{0}, E′, I′, T ran′) be asynchronous transition systems. Suppose that (η, σ) : T → T′ is a morphism. It induces the monoid homomorphism η^{∗} : M(E, I) → M(E′, I′) sending morphisms given by words w = e_{1}e_{2} ⋯ e_{n} into the morphisms given by words η_{∗}(e_{1})η_{∗}(e_{2}) ⋯ η_{∗}(e_{n}) where

η_{∗}(e) = \begin{cases}η(e) , & if e ∈ dom η, \\ ⋆ , & otherwise. \end{cases}

We assign to a morphism of asynchronous transition systems (η, σ) : T → T′ the functors K_{∗}(η, σ) : K_{∗}(T) → K_{∗}(T′) and K(η, σ) : K(T) → K(T′) which are

defined as (s ∈ S ∪{⋆}) ↦ (σ(s) ∈ S′∪{⋆}) on objects and (s_{1} →^{w} s_{2}) ↦ (σ(s_{1}) →^{η^{∗}(w)}

σ(s_{2})) on morphisms.

Since the map σ : S → S′ is totally defined on S, the functor K_{∗}(η, σ) : K_{∗}(T) → K_{∗}(T′) maps objects of K(T) ⊆ K_{∗}(T) into objects of K(T′) ⊆ K_{∗}(T′). These subcategories are full. Therefore K_{∗}(η, σ) determines a functor K(η, σ) : K(T) → K(T′).

Thus any diagram F : K(T) → Ab determines the homology group H_{n}(K(T), F) of the category of states, for every n ⩾ 0. Similarly, the homology group H_{n}(K_{∗}(T), F) of the augmented category of states is associated to any diagram F : K_{∗}(T) → Ab. A morphism of (η, σ) : T → T′ to a diagram G : K(T′) → Ab determines the group homomorphisms H_{n}(K(T), G ∘ K(η, σ)) → H_{n}(K(T′), G). Analogously there is given a homomorphism

H_{n}(K_{∗}(T), G ∘ K_{∗}(η, σ)) → H_{n}(K_{∗}(T′), G)

for a diagram G : K_{∗}(T′) → Ab.

For any diagram F : K(T) → Ab, denote by F_{∗} : K_{∗}(T) → Ab the diagram which has values F_{∗}(s) = F (s), for s ∈ S, and F_{∗}(⋆) = 0.

Example 5.3. We calculate the homology groups for Example 5.2. The category K(T) has a terminal object. Hence, for a diagram F : K(T) → Ab, the groups H_{n}(K(T), F) is equal to 0, for n > 0, and H_{0}(K(T), F) ≅ F (s_{3}).

Now we calculate the homology groups of the augmented category of states. It is clear that H_{0}(K_{∗}(T), F_{∗}) = 0. Since every flow is a sum of internal flows, we have H_{1}(K_{∗}(T), F_{∗}) = 0. According to Corollary 3.5 H_{n}(K_{∗}(T), F_{∗}) = 0, for n ⩾ 3. The group H_{2}(K_{∗}(T), F_{∗}) = 0 is isomorphic to the kernel of d_{1}. In this case d_{1} is a monomorphism. Thus H_{n}(K_{∗}(T), F_{∗}) = 0, for all n ⩾ 0 and for every diagram F of abelian groups on K(T).

Example 5.4. Let T = (S, s_{0}, E, I, T ran) be an asynchronous transition system consisting of a single state s_{0} and a single event e, i.e. S = {s_{0}} and E = {e}. Suppose that I = ∅, T ran = {(s_{0}, e, s_{0})}. Then H_{n}(K_{∗}(T), F_{∗}) ≅ H_{n}(K(T), F), for all n ⩾ 0. It is easy to see that H_{n}(K(T), F) = 0, for n > 1, and H_{1}(K(T), F) is isomorphic to a subgroup of F (s_{0}) which contains all elements f ∈ F (s_{0}) such that F (e)(f) = f.

If I = ∅, then the (augmented) category of states is free. It implies the following.

Proposition 5.1. Let T = (S, s_{0}, E, I, T ran) be an asynchronous transition system and F : K(T) → Ab a diagram. If I = ∅, then H_{1}(K(T), F) (respectively H_{1}(K_{∗}(T), F_{∗})) is isomorphic to the group of flows in the graph (respectively in augmented graph) of states with coefficients in F (F_{∗}). In this case H_{n}(K(T), F) and H_{n}(K_{∗}(T), F_{∗}) vanish for n ⩾ 2.

Definition 5.5. Let N be a CE net and let F : K(U(N)) → Ab be a diagram where U : N → A the above functor from the category of CE nets to the category of asynchronous transition systems. The homology groups of the category of states of N are defined by H_{n}(K(U(N)), F), n ⩾ 0.

A state s ∈ S of an asynchronous transition system (S, s_{0}, E, I, T ran) is said to be reachable if there exists w ∈ E^{∗} such that s_{0} · w = c. Consider Example 4.2 (Fig. 3). The set of objects of K(U(N)) equals 2^{P} where P = {p_{0}, p_{1}, ⋯, p_{5}}. Let F be a diagram with values 0 for the states which are not reachable. Since K(U(N)) is the free category, we have H_{k}(K(U(N)), F) = 0, for k > 1. Since F vanishes for the states which are not reachable, the group consists of flows in the graph

[figure: s_{2}; γ_{4}; γ_{1}; γ_{2}; γ_{3}; s_{4}; s_{1}; s_{0}; γ_{0}; s_{3}]

where s_{0} = {p_{0}, p_{1}, p_{2}}, s_{1} = {p_{1}, p_{2}, p_{5}}, s_{2} = {p_{2}, p_{3}, p_{5}}, s_{3} = {p_{1}, p_{4}, p_{5}}, s_{4} =

{p_{3}, p_{4}, p_{5}}, γ_{0} = (s_{0} →^{t_{0}} s_{1}), γ_{1} = (s_{1} →^{t_{1}} s_{2}), γ_{2} = (s_{1} →^{t_{2}} s_{3}), γ_{3} = (s_{3} →^{t_{1}}

s_{4}), γ_{4} = (s_{2} →^{t_{2}} s_{4}). Considering this group of flows we get H_{1}(K(U(N)), F) = Ker(F (γ_{4}γ_{1}) − F (γ_{3}γ_{2})).

Homology groups of the category of states for the reader and writer problem. The category of states of Example 4.5 is given by the presentation (Γ, R), where Γ is the graph with the set V (Γ) = ℕ × ℕ of vertices and the set A(Γ) consisting of the arrows a_{n}, d_{n}, b_{i j}, c_{i j} defined for n ⩾ 0, i ⩾ 0, j ⩾ 0 by means of dom(a_{n}) = (n, 0), cod(a_{n}) = (n + 1, 0), dom(d_{n}) = (0, n + 1), cod(d_{n}) = (0, n), dom(b_{i j}) = (i + 1, j), cod(b_{i j}) = (i, j), dom(c_{i j}) = (i, j), cod(c_{i j}) = (i, j + 1). The set R contains the pairs (b_{i j+1}c_{i+1 j}, c_{i j}b_{i j}), with i, j ⩾ 0. The graph Γ includes a subgraph Γ_{1} corresponding to the asynchronous transition system

(0, 0) \underleftarrow{d} ; \overrightarrow{c} (0, 1) \underleftarrow{d} ; \overrightarrow{c} (0, 2) \underleftarrow{d} ; \overrightarrow{c} (0, 3) \underleftarrow{d} ; \overrightarrow{c} ⋯
a ↓
(1, 0) \overrightarrow{c} (1, 1) \overrightarrow{c} (1, 2) \overrightarrow{c} (1, 3) \overrightarrow{c} ⋯
a ↓
(2, 0) \overrightarrow{c} (2, 1) \overrightarrow{c} (2, 2) \overrightarrow{c} (2, 3) \overrightarrow{c} ⋯
a ↓
⋯  ⋯  ⋯  ⋯

The set of vertices is V (Γ_{1}) = ℕ × ℕ. The set of arrows A(Γ_{1}) is obtained from A(Γ) by deleting the arrows b_{i j} with i, j ⩾ 0. Let F : PaΓ/R → Ab be a diagram of abelian groups. Suppose that for each i ∈ ℕ there exists j_{0} such that F (i, j) = 0 for all j > j_{0}. Then every flow ∑ f_{γ}[γ] ∈ Φ(Γ_{1}, F) may be regarded as a flow in Γ obtained by the addition zero values f_{γ} = 0 for γ ∈ {b_{i j} : i, j ⩾ 0}. It determines a homomorphism t : Φ(Γ_{1}, F) → H_{1}(PaΓ/R, F).

Proposition 5.2. With the above hypothesis on F, the homomorphism t is an isomorphism.

Proof. We first prove that t is surjective. For each flow ∑ f_{γ}[γ] choose among its summands a member g_{i j}[b_{i j}] with the greatest i for which there is j such that g_{i j} ≠ 0, for some g_{i j} ∈ F (i + 1, j). Then choose the smallest j such that g_{i j} ≠ 0.

Using the commutativity of the diagram:

(i, j)  ⟶^{c_{i j}}  (i, j + 1)
b_{i j} ↑  ↑ b_{i j+1}
(i + 1, j) ⟶^{c_{i+1 j}} (i + 1, j + 1)

we obtain that the difference

(∑ f_{γ}[γ]) − g_{i j}[b_{i j}] − F (b_{i j})(g_{i j})[c_{i j}] + g_{i j}[c_{i+1 j}] + F (c_{i+1 j})(g_{i j})[b_{i j+1}]

is a flow which is equivalent to the flow ∑ f_{γ}[γ]. If we repeat these subtractions every time by choosing (i, j) with above properties, then we obtain a flow which is equivalent to ∑ f_{γ}[γ]. It does not contain the summands g[b_{i j}] with g ≠ 0. Therefore t is surjective.

We prove now that t is injective. We calculate Ker t. Let z be a flow such that t(z) = 0. Then z is a sum of some internal flows

f_{i j}[b_{i j}] + F (b_{i j})(f_{i j})[c_{i j}] − f_{i j}[c_{i+1 j}] − F (c_{i+1 j})(f_{i j})[b_{i j+1}].

Choose among them an internal flow with greatest i, for which there exists j satisfying f_{i j} ≠ 0. Then we take a smallest index among such indices j. Because of z ∈ Φ(Γ_{1}, F) we will get f_{i j}[b_{i j}] = 0, and consequently f_{i j} = 0. The contradiction shows that it follows from t(z) = 0 that z = 0. Thus Ker(t) = 0 and t is an injection.

□

We assume that the first homology group of the category of states for the reader and writer problem is isomorphic to the abelian group of flows Φ(Γ_{1}, F).

For example, if

F (i, j) = \begin{cases}ℤ, & if 0 ⩽ i ⩽ p − 1 and 0 ⩽ j ⩽ q − 1, \\ 0, & otherwise, \end{cases}

and if the diagram F satisfies to the following equalities

F (a_{n}) = 1_{ℤ}, for all 0 ⩽ n ⩽ p − 2,

F (d_{n}) = 1_{ℤ}, for all 0 ⩽ n ⩽ q − 2,

F (b_{i j}) = 1_{ℤ}, for all 0 ⩽ i ⩽ p − 2, 0 ⩽ j ⩽ q − 1,

F (c_{i j}) = 1_{ℤ}, for all 0 ⩽ i ⩽ p − 1, 0 ⩽ j ⩽ q − 2,

then H_{1}(PaΓ/R, F) ≅ ℤ^{p+q−1}.

Kan extensions and homology of partially commutative monoids. Let M be a monoid considered as a category with the single object M. Any right pointed set X over M may be regarded as a functor X : M^{op} → Set_{∗}. Let S : K_{∗}(M, X) → M^{op} be the functor defined as S(x →^{μ} y) = μ. For each diagram F : K_{∗}(M, X) → Ab we have its Kan extension Lan^{S} F : M^{op} → Ab. Every maximal connected subcategory of the category S ↓ M has a terminal object of the form (x, 1) with x ∈ X. Hence Lan^{S} F is the right M-module Lan^{S} F (M) = ⨁_{x∈X} F (x) with the action

f[x] · μ = F (x →^{μ} xμ)(f)[xμ].

The work [11] was devoted to the homology of the augmented category of states. The following assertion is one of its main results. It was proved by means of the Andre spectral sequence. Here we prove it by a rather simple method.

Denote Lan^{S} F by F̃.

Theorem 5.3. Let M be a monoid and X a right pointed set over M. Let F be a diagram of abelian groups on K_{∗}(M, X). Then H_{n}(K_{∗}(M, X), F) ≅ H_{n}(M^{op}, F̃), for all n ⩾ 0, where H_{n}(M^{op}, F̃) is a n-th homology group of the monoid M with coefficients in the right M-module F̃.

Proof. Since the functor Lan^{S} is left adjoint to the exact functor Ab^{S}, it carries projective objects into projective [1, Prop. 6.3]. The sum of exact sequences is exact, consequently Lan^{S} is exact. Hence Lan^{S} carries any projective resolution

0 ← F ← P_{0} ← P_{1} ← ⋯

into a projective resolution of F̃. Applying the functor colim^{M^{op}} to the resolution Lan^{S} P_{∗} of F̃, we will get a complex of abelian groups colim^{M^{op}}(Lan^{S} P_{n}). Therefore H_{n}(colim^{ℂ} Lan^{S} P_{∗}) ≅ H_{n}(M^{op}, Lan^{S} F). Using the isomorphism

colim^{M^{op}}(Lan^{S} P_{∗}) ≅ colim^{K_{∗}(M,X)} P_{∗}

we obtain H_{n}(K_{∗}(M, X), F) ≅ H_{n}(M^{op}, Lan^{S} F) for all n ⩾ 0. □

Homology of asynchronous transition without triples of mutually independent events. Let T = (S, s_{0}, E, I, T ran) be an asynchronous transition system and let n > 0 be a positive integer. We will say that T contains n mutually independent events, if there exists a subset {e_{1}, ⋯, e_{n}} ⊆ E such that (e_{i}, e_{j}) ∈ I for all i ≠ j, 1 ⩽ i, j ⩽ n. Otherwise we say that T does not contain n-tuples of mutually independent events.

It follows from Theorem 1.2 and Corollary 3.5 that if T does not contain triples of mutually independent events, then H_{n}(K_{∗}(T), F) = 0 for all n ⩾ 3 and functors F : K_{∗}(T) → Ab. We prove that this is true for K(T).

Let ℂ be a category. A subcategory 𝔻 ⊆ ℂ is called convex if the following conditions are satisfied:

(i) 𝔻 ⊆ ℂ is a full subcategory;

(ii) if d_{1}, d_{2} ∈ Ob 𝔻 and c ∈ Ob ℂ have morphisms d_{1} → c → d_{2}, then c ∈ Ob 𝔻. It is clear that K(T) and K_{∗}(T) are convex subcategories of K_{∗}(T). For any convex subcategory K ⊆ K_{∗}(T), we consider a set T ran(K) which

consists of all arrows γ of the augmented graph of states such that γ ∈ MorK. In particular T ran(K(T)) = T ran. The set T ran(K_{∗}(T)) consists of all arrows of the augmented graph of states. Let R_{K}(I) contains all pairs (x →^{a} y →^{b} z, x →^{b} y′ →^{a} z) for which (ab, ba) ∈ R(I) and x, z ∈ Ob(K).

Corollary 5.4. Let T = (S, s_{0}, E, I, T ran) be an asynchronous transition system and K ⊆ K_{∗}(T) a convex subcategory. Let F : K → Ab be a functor. If T does not contain triples of mutually independent events, then H_{n}(K, F) = 0 for n ⩾ 3 and H_{n}(K, F) are isomorphic to the homology groups of the following complex for n = 0, 1, 2:

0 → ⨁_{r∈R_{K}(I)} F (dom r) ⟶^{d_{1}} ⨁_{γ∈T ran(K)} F (dom γ) ⟶^{d_{0}} ⨁_{x∈ObK} F (x) → 0. (9)

Proof. We denote by \overline{T ran}(K) the subgraph of the augmented graph which consists of arrows T ran(K). It easy to see that the category K_{∗}(T) has the presentation

(\overline{T ran}(K_{∗}(T)), R_{K_{∗}(T)}(I)).

Using Lemma 1.1 we obtain that (\overline{T ran}(K), R_{K}(I)) is the presentation of K. Let α = α_{n} ⋯ α_{1} and β = β_{n} ⋯ β_{1} are 1-paths in the graph \overline{T ran}(K). Denote M = M(E, I). Let α_{i} = (x_{i−1}, a_{i}, x_{i}) and β_{i} = (x′_{i−1}, b_{i}, x′_{i}) where x_{0} = x′_{0} = x and y_{0} = y′_{0} = y. Since K is convex, the map

Ω_{0}(R_{K}(I))(x, y)(α, β) → Ω_{0}(R(I))(M, M)(a_{n} ⋯ a_{1}, b_{n} ⋯ b_{1})

is bijective and induces the bijection of 2-morphisms. The set Hom_{Ω(R_{K}(I))}(x, y)(α, β) contains at most one element by Theorem 1.2. Hence Ω(R_{K}(I)) is the trivial 2category. Using Corollary 3.5, we complete the proof. □

Homology of asynchronous transition systems and Petri nets. If s_{0} is the initial state of an asynchronous transition system T, we will consider the full subcategory T (s_{0}) ⊆ K(T) of all reachable states. Let ℤ_{T (s_{0})} : K(T) → Ab be a diagram such that ℤ_{T (s_{0})}(s) = ℤ for all reachable states s, and ℤ_{T (s_{0})}(s) = 0 if s ∉ Ob(T (s_{0})). The diagram ℤ_{T (s_{0})} assign to all morphisms of T (s_{0}) the identity homomorphism 1_{ℤ}. Other morphisms are sent to zero homomorphisms. Write H_{n}(T) = H_{n}(K(T), ℤ_{T (s_{0})}), for n ⩾ 0. The group H_{n}(T) will be called the n-th integer homology of T. Each morphism of asynchronous transition systems T → T′ carries the initial state s_{0} into the initial state s′_{0}. Consequently, it induces a morphism (K(T), ℤ_{T (s_{0})}) → (K(T′), ℤ_{T′(s′_{0})}) in the category Dg(Ab). This gives homomorphisms H_{n}(T) → H_{n}(T′), for all n ⩾ 0.

Since T (s_{0}) is a connected category, we have H_{0}(T) = ℤ.

Proposition 5.5. Let T be an asynchronous transition system with an initial state s_{0}. Then for every n ⩾ 0 the group H_{n}(T) is isomorphic to n-th homology group of the nerve of the category T (s_{0}).

Proof. Recall that for arbitrary small category ℂ the functor Δ_{ℂ}ℤ : ℂ → Ab has the value ℤ at each c ∈ Ob ℂ and the value 1_{ℤ} at each α ∈ Mor ℂ. The subcategory T (s_{0}) ⊆ K(T) contains for any s ∈ Ob(T (s_{0})) all objects s′ ∈ S for which there exist s → s′. Hence the complexes C_{n}(K(T), ℤ_{T (s_{0})}) and C_{n}(T (s_{0}), Δ_{T (s_{0})}ℤ) are isomorphic. It is well known [2] that for every category ℂ the homology of the nerve of ℂ may be defined as H_{n}( ℂ, Δ_{ℂ}ℤ). Substituting ℂ = T (s_{0}) we get the required result. □

The group H_{1}(T) may be calculated by means of Smith normal form for the differential d_{1} of Theorem 3.2. This allows us to calculate the first homology group of a Petri net.

Definition 5.6. Let N be a CE net and n ⩾ 0 an integer. The n-th homology group H_{n}(N) of the CE net N is the integral homology group H_{n}(U(N)) where U(N) is the asynchronous transition system defined in the end of Section 4.

For example, consider a pipeline consisting of the three threads (processes) a, b, c which transfer data by means of common integer variables p and q. Suppose that f and g are functions ℕ → ℕ. The thread a computes p := f(n) for n = 0, 1, ⋯; the thread b computes q := g(p); the thread c displays the values of q. Each computing executes a random run time. The states are described by the following CE net denoted N:

[figure: p; q; a; b; c]

The functor U : N → A assign to N an asynchronous transition system with the following graph of states:

[figure: ∅; c; a; c; a; {q}; {p}; b; {p, q}]

Here U(N) = (S, s_{0}, E, I, T ran) has S = {∅, {p}, {q}, {p, q}}, s_{0} = ∅, E = {a, b, c}, I = {(a, c), (c, a)}. The set T ran contains triples corresponding to the arrows of graph of states: γ_{1} = (∅ →^{a} {p}), γ_{2} = ({q} →^{c} ∅), γ_{3} = ({q} →^{a} {p, q}),

γ_{4} = ({p, q} →^{c} {p}), γ_{5} = ({p} →^{b} {q}). Let R = {(γ_{2}γ_{1}, γ_{4}γ_{3})}.

Calculate the groups H_{n}(N). Write entries of matrices of homomorphisms

⨁_{r∈R} ℤ ⟶^{d_{1}} ⨁_{γ∈T ran} ℤ ⟶^{d_{0}} ⨁_{s∈S} ℤ .

By Corollary 3.5 we have H_{n}(N) = 0 for n ⩾ 3. The group H_{2}(N) is isomorphic to Ker d_{1}. Denote matrices corresponding to the homomorphisms d_{i} by A_{i}, i ∈ {0, 1}. Any element of ⨁_{γ∈T ran} ℤ is an integer vector. It will be considered as a matrix consisting of a single column. The element d_{0}(z) is a column obtained by the multiplication of A_{0} with a column corresponding to z ∈ ⨁_{γ∈T ran} ℤ. We have

A_{0} = ( \begin{matrix}1 & −1 & 0 & 0 & 0 \\ −1 & 0 & 0 & −1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & −1 & 1 & −1 \end{matrix} ) A_{1} = ( \begin{matrix}1 \\ 1 \\ −1 \\ −1 \\ 0 \end{matrix} )

where the states are corresponded to strings of A_{0} in the following order: ∅, {p}, {q}, {p, q}. The columns are corresponded to transitions in the order γ_{1}, ⋯, γ_{5}. We get a sequence of matrices

0 ⟶^{A_{2}} ℤ ⟶^{A_{1}} ℤ^{5} ⟶^{A_{0}} ℤ^{4}

with A_{2} = 0. Transforming A_{1} and A_{0} to Smith normal form we obtain the matrices:

D(A_{0}) = (\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) D(A_{1}) = (\begin{matrix}1 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix})

According to Proposition 3.7 we have H_{2}(N) = 0, H_{1}(N) ≅ ℤ. Since T (s_{0}) = U(N)(∅) is connected, we have H_{0}(N) ≅ ℤ.

Concluding remarks

We introduced homology groups of asynchronous transition systems as the homology of the category of states with coefficients in some diagram. The existence of the functor U : N → A allowed us to define homology groups for CE nets. Analogously it would have been possible to define homology groups for event structures (in the sense of [26]) or for objects of any category which admits a functor into A. Thus we can obtain information about invariants of these objects such as Betti numbers, Euler characteristic, homological dimension. It is still an open problem to calculate and to interpret these invariants. A CE net is finite if its sets of conditions and events are finite.

Open problem 1. Find an algorithm for the computation of the integer homology groups H_{n}(N) of finite CE nets N for n > 1.

If we built a complex of free finitely generated abelian groups whose homology groups are isomorphic to H_{n}(N), then Open Problem 1 would be solved.

We saw above that H_{0}(N) = ℤ. The group H_{1}(N) may be calculated by means of reduction of the matrices of d_{0} and d_{1} to the Smith normal form. An algorithm for calculating H_{2}(N) when the CE net N does not contain triples of mutually independent events is proposed. The following question is related to this result:

Open problem 2. Let n > 0 be the maximal number of mutually independent events of an asynchronous transition system T. Prove the equality H_{k}(K_{∗}(T), F) = 0 for every diagram F : K_{∗}(T) → Ab and k > n.

We have proved this for n = 1 and n = 2. According to Theorem 5.3 this problem may be reduced to estimating the homological dimension of partially commutative monoids.

Many questions appear in the study of constructions of categories of models for concurrency. We hope that they may be solved by means of classical spectral sequences related to the homology of small categories.

References

[1] Bucur I., Deleanu A. Introduction to the theory of categories and functors. London-New York-Sydney: Interscience, 1968.

[2] Gabriel P., Zisman M. Calculus of fractions and homotopy theory. Berlin-Heidelberg-New York: Springer-Verlag, 1971.

[3] Gaucher P. Homotopy invariants of higher dimensional categories and concurrency in computer science. Math. Structures Comput. Sci. 2000. V.10, N 4. P. 481–524.

[4] Gaucher P. About the globular homology of higher dimensional automata. Cah. Topol. Geom. Differ. 2002. V.43, N2. P.107–156.

[5] Goubault E. The Geometry of Concurrency. PhD thesis, Ecole Normale Supérieure, 1995. 349 pp. http://www.dmi.ens.fr/∼goubault

[6] Havas G., Majewski B.S. Integer Matrix Diagonalization. J. Symbolic Computation. 1997. V.24, N 3/4. P. 399–408.

[7] Hilton P. J., Stammbach U. A Course in Homological Algebra. New York-Heidelberg-Berlin: Springer-Verlag, 1971. (Graduate Texts in Mathematics 4).

[8] Husainov A. Homological dimension theory of small categories. J. Math. Sci., New York. 2002. V. 110, N 1. P. 2273–2321. http://www.kluweronline.com

[9] Husainov A., Calisici H. Flows in Graphs and the Homology of Free Categories. Algebra and Discrete Math. 2003. N 2. P. 36–46. http://adm.lgpu.lg.ua

[10] Husainov A. A., Mikhailova N. N. Architecture of computer systems. Komsomolosk-On-Amur: Komsomolsk-on-Amure State Technical University, 2004. (Russian)

[11] Husainov A. A., Tkachenko V. V. Homology groups of asynchronous transition systems. Mathematical modeling and the near questions of mathematics. Collection of the scientifics works. Khabarovsk: KhGPU, 2003. P. 23–33. (Russian) http://www.knastu.ru/husainov site/index.html

[12] Isbell J. Exact colimits I. Ann. of Math. 1974. V.100, N 2. P. 633 – 637.

[13] Isbell J., Mitchell B. Exact colimits. Bull. Amer. Math. Soc. 1973. V.79. P. 994 – 996.

[14] Isbell J., Mitchell B. Exact colimits and fixed points. Trans. Amer. Math. Soc. 1976. V.220. P. 289 – 298.

[15] Mac Lane S. Homology. Berlin-Göttingen-Heidelberg: Springer-Verlag, 1963.

[16] Mac Lane S. Categories for the Working Mathematician. New York-Heidel-berg-Berlin: Springer-Verlag, 1972 (Graduate Texts in Mathematics 5).

[17] Malbos P. Rewriting Systems and Hochschild-Mitchell Homology. Electronic Notes in Theoretical Computer Science. 2003. V.81. 14 pp. http://www1.elsevier.com/gej-ng/31/29/23/139/23/28/81006.ps [18] Mitchell B. Rings with several objects. Adv. Math. 1972. V.8. P.1-161.

[19] Morace F. Finitely presented categories and homology. Tech.report, Univ. Joseph Fourier. 1995. 27pp. http://www-fourier.ujf-grenoble.fr/PREP/html/a295/a295.html

[20] Naudin P., Quitté C. Algorithmique algébrique. Avec exercices corrigés. Paris-Milan-Barcelone-Bonn: Masson, 1992.

[21] Nielsen M., Winskel G. Petri Nets and Bisimulations. Theoretical Computer Science. 1996. V.153, N 1-2. P. 211–244.

[22] Oberst U. Exactness of inverse limits. Bull. Amer. Math. Soc. 1968. V.74, N.6. P.1129–1132.

[23] Oberst U. Homology of categories and exactness of direct limits. Math. Z. 1968. Bd. 107. S.87–115.

[24] Seifert H., Threlfall W. Lehrbuch der Topologie. Leipzig: Teubner, 1934.

[25] Street R. Categorical Structures. Handbook of Algebra, Vol. I, ed. M. Hazewinkel. Amsterdam: Elsevier, 1996. P. 529–577.

[26] Winskel G., Nielsen M. Models for Concurrency. Handbook of Logic in Computer Science, Vol. IV, ed. Abramsky, Gabbay and Maibaum. Oxford University Press, 1995. P.1–148.

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/2004/n1a22/v6n1a22.(dvi,ps,pdf)

Ahmet A. Husainov husainov@knastu.ru

Department of Computer Technologies Komsomolsk-on-Amur State Technical University Russia Komsomolsk-on-Amur prosp. Lenina, 27, Komsomolsk-on-Amur, Russia, 681013