# Homology and Bisimulation of Asynchronous Transition Systems and Petri Nets
111This work was performed as a part of the Strategic Development Program at
the National Educational Institutions of the Higher Education, N 2011-PR-054

Ahmet A. Husainov

###### Abstract

Homology groups of labelled asynchronous transition systems and Petri nets are
introduced. Examples of computing the homology groups are given. It is proved
that if labelled asynchronous transition systems are bisimulation equivalent,
then they have isomorphic homology groups. A method of constructing a Petri
net with given homology groups is found.

2000 Mathematics Subject Classification 18G35, 18B20, 55U10, 55U15, 68Q85

Keywords: bisimulation, homology groups, simplicial complex, trace monoid,
partial action, asynchronous system, Petri net.

## Introduction

The paper is devoted to the application of algebraic topology methods for
classification and studying the mathematical models of concurrency. We
consider asynchronous transition systems with label functions on events. Our
purpose is to construct a homology theory of labelled asynchronous transition
systems for which any bisimulation equivalent asynchronous transition systems
have isomorphic homology groups.

We consider a categorical notion of the bisimulation defined by open maps [1].
It was proved in [1], that in the case of labelled transition systems this
definition coincides with a strong bisimulation of R. Milner [2]. A
characterization of the bisimilation equivalence for asynchronous transition
systems was given in [3].

Homology groups have no less than important for the classification and
studying the properties of concurrent systems. In particular, they have been
applied in the work [4] to characterize the condition of solvability for some
classes of problems in parallel distribution systems.

In [5], E. Goubault and T. P. Jensen applied homology groups for studying
higher dimensional automata. There were obtained some signs of bisimulation
equivalence for the higher dimensional automata in terms of the homology
groups [5, Prop. 10]. The results were developed in the [6]. In a survey [7],
open questions were marked on the relationship of the Goubault homology [6]
with directed homotopy. The Goubault homology have been applied also to prove
of homotopy properties for higher dimensional automata in the [8].
Communications between homotopy and bisimilarity of higher dimensional
automata was researched in [9].

These groups were used to find signs of parallelizable asynchronous systems in
[11] and were regarded as the homology groups of a topological space of
intermediate states for an asynchronous system in [12]. An algorithm for
computing the homology groups was developed in [13].

In this paper, we study the homology of the labelled asynchronous transition
systems and Petri nets.

We work in the category of asynchronous transition systems considered in [14].
But we call them simply asynchronous systems. Note that M.A. Bednarczyk [15]
studied the broader category of asynchronous systems. Using results of M.
Nielsen and G. Winskel [3], we study open morphisms. We introduce homology
groups for labelled asynchronous transition systems and Petri nets. We prove
that $Pom_{L}$-bisimilar asynchronous transition systems have isomorphic
homology groups (Theorem 3.1 and Corollary 3.2). We give some examples of
computing the homology groups of asynchronous transition systems and Petri
nets. We prove that for an arbitrary finite sequence of finitely generated
Abelian groups $A_{0}$, $A_{1}$, $A_{2}$, …where $A_{0}$ is free and not equal
$0$ there exists a labelled Petri net the $i$th homology groups of which are
isomorphic to $A_{i}$ for all $i\geqslant 0$.

###### Contents

  1. 1 Asynchronous systems and trace monoid actions
    1. 1.1 State spaces and asynchronous systems
    2. 1.2 Asynchronous systems and partial actions of trace monoids
    3. 1.3 Open morphisms
  2. 2 Bisimulation equivalence of labelled asynchronous systems
    1. 2.1 Labelled asynchronous systems
    2. 2.2 Open maps and surjectivity
  3. 3 Homology groups of asynchronous systems
    1. 3.1 Computing homology groups of simplicial schemes
    2. 3.2 Homology groups of labelled asynchronous systems
  4. 4 Homology groups of labelled Petri nets
    1. 4.1 Petri nets
    2. 4.2 Labelled asynchronous system for a Petri net and its homology groups

##  1 Asynchronous systems and trace monoid actions

Let us recall some facts on the mathematical models of concurrency [3], [14],
[15]. We study asynchronous systems as trace monoids with partial action on
sets.

###  1.1 State spaces and asynchronous systems

###### Definition 1.1

A state space $(S,E,I,{\rm Tran})$ consists of a set $S$ of states, a set $E$
of events with a symmetric irreflexive relation $I\subseteq E\times E$ of
independence, and a transition relation ${\rm Tran}\subseteq S\times E\times
S$. The following axioms must be satisfied:

  1. (i)

If $(s,a,s^{\prime})\in{\rm Tran}$ $\&$ $(s,a,s^{\prime\prime})\in{\rm Tran}$,
then $s^{\prime}=s^{\prime\prime}$.

  2. (ii)

If $(a,b)\in I~{}\&~{}(s,a,s^{\prime})\in{\rm
Tran}~{}\&~{}(s^{\prime},b,s^{\prime\prime})\in{\rm Tran}$, then there exists
$s_{1}\in S$ such that $(s,b,s_{1})\in{\rm Tran}$ $\&$
$(s_{1},a,s^{\prime\prime})\in{\rm Tran}$. (See Fig. 1)

---
$\textstyle{s^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\scriptstyle{b}$$\textstyle{s^{\prime\prime}}$$\textstyle{s_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$

Figure 1: To Axiom (ii)

.

Triples $(s,e,s^{\prime})\in{\rm Tran}$ are denoted by
$s\stackrel{{\scriptstyle e}}{{\to}}s^{\prime}$ and called transitions .

###### Definition 1.2

Asynchronous system ${\mathcal{A}}=(S,s_{0},E,I,{\rm Tran})$ is a state space
$(S,E,I,{\rm Tran})$ with a distinguished initial state $s_{0}\in S$.
Moreover, for every $a\in E$, there must be $s_{1},s_{2}\in S$ satisfying
$(s_{1},a,s_{2})\in Tran$.

###### Definition 1.3

A morphism between state spaces

$(\sigma,\eta):(S,E,I,{\rm Tran})\to(S^{\prime},E^{\prime},I^{\prime},{\rm
Tran}^{\prime})$

is a pair consisting of a partial map $\eta:E\rightharpoonup E^{\prime}$ and a
map $\sigma:S\to S^{\prime}$ satisfying the following conditions

  1. (i)

for any triple $(s_{1},e,s_{2})\in{\rm Tran}$, there is the following
alternative

$\left\\{\begin{array}[]{cl}(\sigma(s_{1}),\eta(e),\sigma(s_{2}))\in{\rm
Tran}^{\prime},&\mbox{ if the value }\eta(e)\mbox{ is defined},\\\
\sigma(s_{1})=\sigma(s_{2}),&\mbox{ if }\eta(e)\mbox{ is not
defined};\end{array}\right.$

  2. (ii)

for all $(e_{1},e_{2})\in I$, if $\eta(e_{1})$ and $\eta(e_{2})$ both are
defined, then $(\eta(e_{1}),\eta(e_{2}))\in I^{\prime}$.

Let ${\mathcal{A}}=(S,s_{0},E,I,{\rm Tran})$ and
${\mathcal{A}}^{\prime}=(S^{\prime},s^{\prime}_{0},E^{\prime},I^{\prime},{\rm
Tran}^{\prime})$ be asynchronous systems. A morphism of asynchronous systems
$(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is a mophism
$(\sigma,\eta):(S,E,I,{\rm Tran})\to(S^{\prime},E^{\prime},I^{\prime},{\rm
Tran}^{\prime})$ between the state spaces such that
$\sigma(s_{0})=s^{\prime}_{0}$.

###  1.2 Asynchronous systems and partial actions of trace monoids

Below, throughout the paper, we will denote ${\mathcal{A}}=(S,s_{0},E,I,{\rm
Tran})$ and
${\mathcal{A}}^{\prime}=(S^{\prime},s^{\prime}_{0},E^{\prime},I^{\prime},{\rm
Tran}^{\prime})$.

For an arbitrary category $\cal C$, let ${\cal C}^{op}$ be the opposite
category.

Denote by $PSet$ the category of sets and partial maps. Let $M$ be a monoid
considered as the category with a single object. A partial right action of a
monoid $M$ on a set $S$ is a functor $M^{op}\to PSet$, the value of which on
the single object is equal to $S$. The functor assigns to each morphism
$\mu\in M$ a partial map $S\rightharpoonup S$ the values of which defined on
$s\in S$ are denoted by $s\cdot\mu$. The category $PSet$ is equivalent to the
category of pointed sets and pointed maps [14]. If we leave pointed sets,
whose distinguished points are equal to a fixed common point $*$, then we
obtain a category isomorphic to the category $PSet$. We denote this category
by ${\rm Set}_{*}$. The isomorphism allows us to consider a partial right
action of $M$ on $S$ as a functor $M^{op}\to{\rm Set}_{*}$. We denote this
functor by $(M,S_{*})$. For each $\mu\in M$, its value $(M,S_{*})(\mu)$ is the
map denoted by $s\mapsto s\cdot\mu$ for all $s\in S_{*}$.

In particular, the state space can be considered as a set with a partial
action of a trace monoid. Let us recall the definition of a trace monoid [16].

Let $E$ be a set with a symmetric irreflexive relation $I\subseteq E\times E$.
Denote by $E^{*}$ a free monoid of words with the letters of $E$. Elements
$a,b\in E$ are independent if $(a,b)\in I$. We define an equivalence relation
on $E^{*}$ assuming $w_{1}\equiv w_{2}$ if the word $w_{2}$ can be obtained
from $w_{1}$ by a finite sequence permutations of adjacent independent
elements. Let $[w]$ be the equivalence class of $w\in E^{*}$. It is easy to
see that the operation $[w_{1}][w_{2}]=[w_{1}w_{2}]$ transforms the set of
equivalence classes $E^{*}/\equiv$ in a monoid. This monoid is called a trace
monoid $M(E,I)$.

Let $(S,E,I,{\rm Tran})$ be a state space. For any $s\in S$ and $e\in E$,
there exists at most one $s^{\prime}\in S$ for which $(s,e,s^{\prime})\in{\rm
Tran}$. In this case, we set $s\cdot e=e^{\prime}$. If ${\rm Tran}$ does not
contain such a triple, then let $s\cdot e=*$. Now we can assign to each state
space $(S,E,I,{\rm Tran})$ the partial action $(M(E,I),S_{*})$ defined as
$(s,[e_{1}\cdots e_{n}])\mapsto(\ldots((s\cdot e_{1})\cdot e_{2})\ldots\cdot
e_{n})$. Any asynchronous system can be considered as a partial action
$(M(E,I),S_{*})$ of the trace monoid on $S$ with initial element $s_{0}\in S$.
It follows from the definition of action that the formula $s\cdot e\in S$ is
equivalent to $(\exists t\in S)(s,e,t)\in{\rm Tran}$. This formula means that
the value $s\cdot e$ is defined, but $s\cdot e=*$ means that this value is not
defined. The morphism between asynchronous systems
${\mathcal{A}}\to{\mathcal{A}}^{\prime}$ can be defined as a pair of maps
$\sigma:S\to S^{\prime}$, $\eta:E\to E^{\prime}\cup\\{1\\}$ for which

  * •

the map $\eta$ can be extended to a homomorphism of monoids $M(E,I)\to
M(E^{\prime},I^{\prime})$;

  * •

for every $s\in S$ and $e\in E$ satisfying $s\cdot e\in S$, it is true that
$\sigma(s)\cdot\eta(e)\in S~{}\&~{}\sigma(s)\cdot\eta(e)=\sigma(s\cdot e)$;

  * •

$\sigma(s_{0})=s^{\prime}_{0}$.

###  1.3 Open morphisms

A state $s\in S$ of asynchronous system ${\mathcal{A}}$ is reachable if there
exists a finite sequence of transitions $s_{0}\stackrel{{\scriptstyle
e_{1}}}{{\to}}s_{1}\stackrel{{\scriptstyle e_{2}}}{{\to}}s_{2}\to\cdots\to
s_{n-1}\stackrel{{\scriptstyle e_{n}}}{{\to}}s$.

If we want to emphasize that the map $f:X\to Y$ is defined on all elements of
$X$, then we call it total.

###### Definition 1.4

A morphism of asynchronous systems
$(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is open, if it has the
following properties:

  1. (i)

$\eta:E\to E^{\prime}$ is total;

  2. (ii)

for all a state $s\in S$ and transition
$(\sigma(s),e^{\prime},u^{\prime})\in{\rm Tran}^{\prime}$, there exists
$(s,e,u)\in{\rm Tran}$ for which $\eta(e)=e^{\prime}$ and
$\sigma(u)=u^{\prime}$;

  3. (iii)

for any reachable $s\in S$, if $(s,e_{1},u)\in{\rm Tran}$ and
$(u,e_{2},v)\in{\rm Tran}$ and $(\eta(e_{1}),\eta(e_{2}))\in I^{\prime}$, then
$(e_{1},e_{2})\in I$.

The property (ii) can be shown visually by drawing

---
$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\exists\,e}$$\textstyle{\sigma(s)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\forall\,e^{\prime}}$$\scriptstyle{\eta}$$\textstyle{u}$$\textstyle{u^{\prime}}$

For any asynchronous system ${\mathcal{A}}=(S,s_{0},E,I,{\rm Tran})$ and a
reachable $s\in S$, we let ${\mathcal{A}}(s)=(S,s,E,I,{\rm Tran})$. In
particular, ${\mathcal{A}}(s_{0})={\mathcal{A}}$.

###### Proposition 1.1

For any open morphism $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$
of asynchronous systems and a reachable state $s\in S$, the morphism
$(\sigma,\eta):{\mathcal{A}}(s)\to{\mathcal{A}}^{\prime}(\sigma(s))$ is open.

##  2 Bisimulation equivalence of labelled asynchronous systems

In this section, we consider $Pom_{L}$-bisimilar labelled asynchronous
systems.

###  2.1 Labelled asynchronous systems

A labelled asynchronous system $({\mathcal{A}},\lambda,L)$ consists of an
asynchronous system ${\mathcal{A}}$ with an arbitrary set $L$ of labels and a
map $\lambda:E\to L$ called label function. Each asynchronous system can be
considered as labelled where the set $L=pt$ consists of a single label. In
this sense, according to [3, Prop. 16], open morphisms are precisely
$Pom_{pt}$-open morphisms.

Let $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ be labelled asynchronous
systems. A morphism $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$
preserves labels , if for all $e\in E$, it satisfies to equality
$\lambda(e)=\lambda^{\prime}(\eta(e))$. In this case, the pair $(\sigma,\eta)$
is called a morphism of labelled asynchronous systems
$({\mathcal{A}},\lambda,L)\to({\mathcal{A}}^{\prime},\lambda^{\prime},L)$.

The following statement is a reformulation of the characterization of
$Pom_{L}$-morphisms given in [3, Prop.16].

###### Proposition 2.1

A morphism
$(\sigma,\eta):({\mathcal{A}},\lambda,L)\to({\mathcal{A}}^{\prime},\lambda^{\prime},L)$
between labelled asynchronous systems is $Pom_{L}$-open if and only if the
morphism $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is open and
preserves labels.

This proposition allows us to mean by $Pom_{L}$-open morphisms the open
morphisms, preserving labels.

###### Definition 2.1

[3] Let $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ be labelled asynchronous
systems. If there exists a labelled asynchronous system
$({\mathcal{A}}^{\prime\prime},\lambda^{\prime\prime},L)$ with $Pom_{L}$-open
morphisms
$({\mathcal{A}}^{\prime\prime},\lambda^{\prime\prime},L)\stackrel{{\scriptstyle(\sigma,\eta)}}{{\to}}({\mathcal{A}},\lambda,L)$
and
$({\mathcal{A}}^{\prime\prime},\lambda^{\prime\prime},L)\stackrel{{\scriptstyle(\sigma^{\prime},\eta^{\prime})}}{{\to}}({\mathcal{A}}^{\prime},\lambda^{\prime},L)$,
then $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ are called $Pom_{L}$-bisimilar.

###### Proposition 2.2

Let $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ be $Pom_{L}$-bisimilar labelled
asynchronous systems. For every $a_{1}\in E$ satisfying $s_{0}\cdot a_{1}\in
S$, there exists $a^{\prime}_{1}\in E^{\prime}$ such that the following two
properties hold:

  * •

$s^{\prime}_{0}\cdot a^{\prime}_{1}\in S^{\prime}$;

  * •

labelled asynchronous systems $({\mathcal{A}}(s_{1}),\lambda,L)$ and
$({\mathcal{A}}(s^{\prime}_{0}\cdot a^{\prime}_{1}),\lambda^{\prime},L)$ are
$Pom_{L}$-bisimilar.

Proof. Given labelled asynchronous systems are $Pom_{L}$-bisimilar. Hence,
there are $({\mathcal{A}}^{\prime\prime},\lambda^{\prime\prime},L)$ and
$Pom_{L}$-open morphisms

$({\mathcal{A}},\lambda,L)\stackrel{{\scriptstyle(\sigma,\eta)}}{{\longleftarrow}}({\mathcal{A}}^{\prime\prime},\lambda^{\prime\prime},L)\stackrel{{\scriptstyle(\sigma^{\prime},\eta^{\prime})}}{{\longrightarrow}}({\mathcal{A}}^{\prime},\lambda^{\prime},L).$

Morphism $(\sigma,\eta)$ is open. It follows by property (ii) of Definition
1.4 that there exists a transition
$(s^{\prime\prime}_{0},a^{\prime\prime}_{1},s^{\prime\prime}_{1})$ satisfying
conditions $\eta(a^{\prime\prime}_{1})=a_{1}$ and
$\sigma(s^{\prime\prime}_{1})=s_{1}$ (Fig. 2). In other words, there exists
$a^{\prime\prime}_{1}\in E^{\prime\prime}$ such that
$\eta(a^{\prime\prime}_{1})=a_{1}$ and $\sigma(s^{\prime\prime}_{0}\cdot
a^{\prime\prime}_{1})=s^{\prime\prime}_{1}$. By Proposition 1.1, the morphism
$(\sigma,\eta):{\mathcal{A}}^{\prime\prime}(s^{\prime\prime}_{1})\to{\mathcal{A}}(s_{1})$
is open.

$\textstyle{s_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{1}}$$\textstyle{s^{\prime\prime}_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{a^{\prime\prime}_{1}}$$\scriptstyle{\sigma^{\prime}}$$\textstyle{s^{\prime}_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta^{\prime}(a^{\prime\prime}_{1})}$$\textstyle{s_{1}}$$\textstyle{s^{\prime\prime}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{~{}~{}\sigma}$$\scriptstyle{\sigma^{\prime}}$$\textstyle{\sigma^{\prime}(s^{\prime\prime}_{1})}$
Figure 2: To the construction of open morphisms.

The map $\sigma^{\prime}$ of the morphism
$(\sigma^{\prime},\eta^{\prime}):{\mathcal{A}}^{\prime\prime}\to{\mathcal{A}}^{\prime}$
is total. It follows that $\sigma^{\prime}(s^{\prime\prime}_{1})\in
S^{\prime}$. By Proposition 1.1, the morphism
$(\sigma,\eta):{\mathcal{A}}^{\prime\prime}(s^{\prime\prime}_{1})\stackrel{{\scriptstyle(\sigma^{\prime},\eta^{\prime})}}{{\to}}{\mathcal{A}}^{\prime}(\sigma^{\prime}(s^{\prime\prime}_{1}))$
is open. The morphisms $(\sigma,\eta)$ and $(\sigma^{\prime},\eta^{\prime})$
preserve labels. By putting
$a^{\prime}_{1}=\eta^{\prime}(a^{\prime\prime}_{1})$ and
$s^{\prime}_{1}=\sigma^{\prime}(s^{\prime\prime}_{1})$, we obtain the desired.
$\Box$

###### Corollary 2.3

Let $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ be labelled asynchronous
systems. For every $w=a_{1}\cdots a_{k}\in E^{*}$ with $k\geqslant 0$
satisfying the condition $s_{0}\cdot w\in S$, there exists a word
$w^{\prime}=a^{\prime}_{1}\cdots a^{\prime}_{k}\in E^{\prime*}$ such that the
following two properies hold:

  * •

$s^{\prime}_{0}\cdot w^{\prime}\in S^{\prime}$;

  * •

the labelled asynchronous systems $({\mathcal{A}}(s_{0}\cdot w),\lambda,L)$
and $({\mathcal{A}}^{\prime}(s^{\prime}_{0}\cdot
w^{\prime}),\lambda^{\prime},L)$ are $Pom_{L}$-bisimilar.

Proof. For $k=0$, the word $w$ is empty, that is $w=1$. Taking $w^{\prime}=1$,
we get the $Pom_{L}$-bisimilar labelled asynchronous systems
$({\mathcal{A}},\lambda,L)$ and $({\mathcal{A}}^{\prime},\lambda^{\prime},L)$.
For $k=1$, the assertion follows from Proposition 2.2. Assuming that the
assertion is true for some $k>0$, we can prove by Proposition 2.2, that it
holds for $k+1$. So, it is true for all $k\geqslant 0$. $\Box$

###  2.2 Open maps and surjectivity

Let ${\mathcal{A}}$ be an asynchronous system. Denote by
$Q_{0}({\mathcal{A}})=S(s_{0})$ the set of all reachable states $s\in S$. For
every $n>0$, we consider sets

$Q_{n}({\mathcal{A}})=\\{(s,e_{1},\cdots,e_{n})\in S(s_{0})\times E^{n}\\\
s\cdot e_{1}\cdots e_{n}\in S~{}\&~{}(e_{i},e_{j})\in I\mbox{ for all
}1\leqslant i<j\leqslant n\\}$

Let $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ be a morphism of
asynchronous system. If $\eta:E\to E^{\prime}$ is total, then for all
$n\geqslant 0$ the maps $Q_{n}(\sigma,\eta):Q_{n}({\mathcal{A}})\to
Q_{n}({\mathcal{A}}^{\prime})$ are defined by the formula

$Q_{n}(\sigma,\eta)(s,e_{1},\cdots,e_{n})=(\sigma(s),\eta(e_{1}),\cdots,\eta(e_{n})).$

###### Lemma 2.4

If $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is open, then for
every reachable $s^{\prime}\in S^{\prime}$ there exists $s\in S$ such that
$\sigma(s)=s^{\prime}$.

Proof. We have $\sigma(s_{0})=s^{\prime}_{0}$. If $s^{\prime}$ is reachable,
then there exists a path $\sigma(s_{0})=s^{\prime}_{0}\stackrel{{\scriptstyle
a^{\prime}_{1}}}{{\to}}s^{\prime}_{1}\to\cdots\to
s^{\prime}_{n-1}\stackrel{{\scriptstyle
a^{\prime}_{n}}}{{\to}}s^{\prime}_{n}$. The morphism $(\sigma,\eta)$ is open.
Hence for $a^{\prime}_{1}$ and $s^{\prime}_{1}$, there are $a_{1}$ and $s_{1}$
satisfying $\eta(a_{1})=a^{\prime}_{1}$ and $\sigma(s_{1})=s^{\prime}_{1}$.
Then we find $a_{2}\in E$ satisfying $\eta(a_{2})=a^{\prime}_{2}$. And so on
till we find $a_{n}\in E$ such that $\eta(a_{n})=a^{\prime}_{n}$ and
$\sigma(s_{n})=s^{\prime}$. Desired element $s$ will be equal to $s_{n}$.
$\Box$

###### Proposition 2.5

If a morphism $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is open,
then the maps $Q_{n}({\mathcal{A}})\to Q_{n}({\mathcal{A}}^{\prime})$ are
surjective.

Proof. Prove for $n=0$. If $s^{\prime}$ is reachable, then there exists a path

$\sigma(s_{0})=s^{\prime}_{0}\stackrel{{\scriptstyle
a^{\prime}_{1}}}{{\to}}s^{\prime}_{1}\stackrel{{\scriptstyle
a^{\prime}_{2}}}{{\to}}\ldots\stackrel{{\scriptstyle
a^{\prime}_{n}}}{{\to}}s^{\prime}_{k}=s^{\prime}.$

There are $a_{1}\in E$ and $s_{1}\in S$ for which $\eta(a_{1})=a^{\prime}_{1}$
and $(\sigma,\eta)(s_{0}\stackrel{{\scriptstyle
a_{1}}}{{\to}}s_{1})=(s^{\prime}_{0}\stackrel{{\scriptstyle
a^{\prime}_{1}}}{{\to}}s^{\prime}_{1})$:

$\textstyle{s_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{1}}$$\scriptstyle{\sigma}$$\textstyle{s^{\prime}_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a^{\prime}_{1}}$$\textstyle{s_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\textstyle{s^{\prime}_{1}}$

We have $\sigma(s_{1})=s^{\prime}_{1}$. There are $a_{2}\in E$ and $s_{2}\in
S$ satisfying $\sigma(s_{2})=s^{\prime}_{2}$ and $\eta(a_{2})=a^{\prime}_{2}$
and so on. By induction, we obtain $s_{k}\in S$ such that
$\sigma(s_{k})=s^{\prime}_{k}=s^{\prime}$. Therefore, $\sigma:S(s_{0})\to
S^{\prime}(s^{\prime}_{0})$ is surjective.

For $n=1$, the map $\\{(s,e_{1})|se_{1}\in
S\\}\to\\{(\sigma(s),e^{\prime}_{1})|\sigma(s)e^{\prime}_{1}\in S^{\prime}\\}$
is surjective by property (ii) of open morphisms.

Let $n\geqslant 2$. For each $s\in S(s_{0})$, consider the set

$Q_{n}({\mathcal{A}},s)=\\{(s,e_{1},\cdots,e_{n})\in\\{s\\}\times E^{n}~{}|\\\
s\cdot e_{1}\cdots e_{n}\in S~{}\&~{}(e_{i},e_{j})\in I\mbox{ for all
}1\leqslant i<j\leqslant n\\}$

and

$Q_{n}({\mathcal{A}}^{\prime},\sigma(s))=\\{(\sigma(s),e^{\prime}_{1},\cdots,e^{\prime}_{n})\in\\{\sigma(s)\\}\times{E^{\prime}}^{n}|\\\
\sigma(s)\cdot e^{\prime}_{1}\cdots e^{\prime}_{n}\in
S^{\prime}~{}\&~{}(e^{\prime}_{i},e^{\prime}_{j})\in I\mbox{ for all
}1\leqslant i<j\leqslant n.\\}$

For any $(\sigma(s),e^{\prime}_{1},\cdots,e^{\prime}_{n})\in
Q_{n}({\mathcal{A}}^{\prime},\sigma(s))$, there are $e_{1}$, $e_{2}$, …,
$e_{n}\in E$ for which $s_{1}=s\cdot e_{1}\in S$, $s_{2}=s\cdot e_{1}e_{2}\in
S$, …, $s_{n}=s\cdot e_{1}\cdots e_{n}\in S$, wherein
$\eta(e_{1})=e^{\prime}_{1}$, …, $\eta(e_{n})=e^{\prime}_{n}$.

By induction on $n$, we will prove that $(e_{i},e_{j})\in I$ for all
$1\leqslant i<j\leqslant n$. For this purpose, we assume that
$(e_{i},e_{j})\in I$ for all $1\leqslant i<j\leqslant n-1$. And we show that
$(e_{i},e_{n})\in I$ for all $1\leqslant i\leqslant n-1$. We have
$(s_{n-2},e_{n-1},s_{n-1})\in{\rm Tran}$, $(s_{n-1},e_{n},s_{n})\in{\rm
Tran}$, and $(\eta(e_{n-1}),\eta(e_{n}))\in I^{\prime}$. It follows by the
property (iii) that $(e_{n-1},e_{n})\in I$. By Axiom (ii) for a state space,
there is $t\in S$ such that $(s_{n-2},e_{n},t)\in{\rm Tran}$ and
$(t,e_{n-1},s_{n})\in{\rm Tran}$. It follows from
$(\eta(e_{n-2}),\eta(e_{n}))\in I^{\prime}$, that $(e_{n-2},e_{n})\in I$.
Again by Axiom (ii), there is $t_{1}\in S$ such that
$(s_{n-3},e_{n},t_{1})\in{\rm Tran}$ and $(t_{1},e_{n-2},s_{n})\in{\rm Tran}$.
It follows from $(\eta(e_{n-3}),\eta(e_{n}))\in I^{\prime}$, that
$(e_{n-3},e_{n})\in I$, and so on. In the end, we obtain $(e_{i},e_{n})\in I$
for all $1\leqslant i\leqslant n-1$. Consequently $(e_{i},e_{j})\in I$ for all
$1\leqslant i<j\leqslant n$. Thus, $(s,e_{1},\ldots,e_{n})\in
Q_{n}({\mathcal{A}},s)$. Therefore for every
$(s^{\prime},e^{\prime}_{1},\ldots,e^{\prime}_{n})\in Q_{n}({\mathcal{A}})$,
there is $(s,e_{1},\ldots,e_{n})\in Q_{n}({\mathcal{A}})$ mapped to
$(s^{\prime},e^{\prime}_{1},\ldots,e^{\prime}_{n})\in Q_{n}({\mathcal{A}})$.
$\Box$

###### Remark 2.2

The converse is not true. There are morphisms $(\sigma,\eta)$, for which the
map $Q_{n}(\sigma,\eta)$ is surjective for all $n\geqslant 0$, but the
$(\sigma,\eta)$ is not $Pom_{pt}$-open. For example, $S=\\{s_{0}\\}$,
$E=\\{a,b,c\\}$, $I=\\{(a,b),(b,a)\\}$, $S^{\prime}=\\{s^{\prime}_{0}\\}$,
$E^{\prime}=\\{a^{\prime},b^{\prime}\\}$,
$I^{\prime}=\\{(a^{\prime},b^{\prime}),(b^{\prime},a^{\prime})\\}$. Figure 3
shows the independence graphs and the map $\eta:E\to E^{\prime}$.

$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\eta(b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a}$$\textstyle{c}$$\textstyle{\eta(a)=\eta(c)}$
Figure 3: Example of surjection which is not $Pom_{pt}$

We have $(\eta(b),\eta(c))\in I^{\prime}$, but $(b,c)\notin I$. Hence, the
morphism $(\sigma,\eta)$ is not open.

For an reachable state $s\in S$ of asynchronous system
${\mathcal{A}}=(S,s,E,I,{\rm Tran})$, let ${\mathcal{A}}(s)=(S,s,E,I,{\rm
Tran})$ be the asynchronous system which differs only by the initial state.

###### Corollary 2.6

If $(\sigma,\eta):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is open, then for
each reachable state $s\in S$, the maps $Q_{n}({\mathcal{A}}(s))\to
Q_{n}({\mathcal{A}}^{\prime}(\sigma(s)))$ are surjective for all $n\geqslant
0$.

##  3 Homology groups of asynchronous systems

We introduce the homology groups of labelled asynchronous systems. We will
prove that bisimulation equivalence is stronger than property to have
isomorphic homology groups.

###  3.1 Computing homology groups of simplicial schemes

Recall that a simplicial scheme $(A,{\mathfrak{M}})$ consists of a set $A$ of
vertices and a set ${\mathfrak{M}}$ of finite nonempty subsets $S\subseteq A$
satisfying the following conditions

  * •

$(\forall a\in A)$ $\\{a\\}\in{\mathfrak{M}}$,

  * •

$(\forall S,S^{\prime}\subseteq
A)~{}S\in{\mathfrak{M}}~{}\&~{}S^{\prime}\subseteq S\Rightarrow
S^{\prime}\in{\mathfrak{M}}$.

The elements of $\mathfrak{M}$ are called simplices. For $n\geqslant 0$, a
simplex $S$ is called $n$-dimensional or $n$-simplex if number $|S|$ of its
elements equals $n+1$.

Let $(A,\mathfrak{M})$ be a simplicial scheme. For the computing its homology
groups $H_{n}(A,\mathfrak{M})$, we define an arbitrary total order relation on
$A$. Consider the complex

$0\leftarrow{\,\mathbb{Z}}\mathfrak{M}_{0}\stackrel{{\scriptstyle
d_{1}}}{{\leftarrow}}{\,\mathbb{Z}}\mathfrak{M}_{1}\stackrel{{\scriptstyle
d_{2}}}{{\leftarrow}}{\,\mathbb{Z}}\mathfrak{M}_{2}\leftarrow\cdots\leftarrow{\,\mathbb{Z}}\mathfrak{M}_{n-1}\stackrel{{\scriptstyle
d_{n}}}{{\leftarrow}}{\,\mathbb{Z}}\mathfrak{M}_{n}\leftarrow\cdots$

where
$\mathfrak{M}_{n}=\\{(a_{0},a_{1},\ldots,a_{n})|a_{0}<a_{1}<\cdots<a_{n}~{}\&~{}\\{a_{0},a_{1},\ldots,a_{n}\\}\in\mathfrak{M}\\}$.
Elements of $\mathfrak{M}_{n}$ are called ordered $n$-simplices. Here
${\,\mathbb{Z}}\mathfrak{M}_{n}$ denotes the free Abelian group generated by
ordered $n$-simplices. The differentials $d_{n}$ are defined on ordered
$n$-simplices by the formula

$d_{n}(a_{0},a_{1},\ldots,a_{n})=\sum_{i=0}^{n}(-1)^{i}(a_{0},\ldots,\widehat{a_{i}},\ldots,a_{n})$

where $\widehat{a_{i}}$ denotes the operation of removing the symbol $a_{i}$
from the tuple. We will suppose that the sets of $n$-simplices are finite. In
this case, the differentials $d_{n}$ can be specified using integer matrices.

Each column of the matrix for $d_{n}$ corresponds to a tuple
$(a_{0},a_{1},\ldots,a_{n})\in\mathfrak{M}_{n}$. Each string corresponds to
$(a_{0},\ldots,a_{n-1})\in\mathfrak{M}_{n-1}$. For each column
$(a_{0},a_{1},\ldots,a_{n})$ and string
$(a_{0},\ldots,\widehat{a_{i}},\ldots,a_{n})$, at their intersection, the
entry equals $(-1)^{i}$. Other entries of the matrix equal $0$. For
calculating the homology groups, each matrix $d_{n}$ is reduced to the Smith
normal form. The homology groups $H_{n}=Ker(d_{n})/Im(d_{n+1})$ of this
complex is equal to

${\,\mathbb{Z}}^{|\mathfrak{M}_{n}|-rank(d_{n})-rank(d_{n+1})}\oplus{\,\mathbb{Z}}/\delta_{1}{\,\mathbb{Z}}\oplus\cdots\oplus{\,\mathbb{Z}}/\delta_{r}{\,\mathbb{Z}}$

where $r=rank(d_{n+1})$ and $\delta_{1},\cdots,\delta_{r}$ is the non-zero
diagonal entries of the Smith normal form for the matrix $d_{n+1}$.

###  3.2 Homology groups of labelled asynchronous systems

Let $({\mathcal{A}},\lambda,L)$ be a labelled asynchronous system.

Introduce homology groups of the labelled asynchronous systems. For this
purpose, consider the simplicial scheme $(\lambda^{+}E,{\mathfrak{M}})$ whose
vertices are the elements $\lambda(a)$, where $a\in E$ are elements for which
there are $s,s^{\prime}\in S(s_{0})$ satisfying $(s,a,s^{\prime})\in{\rm
Tran}$. Thus

$\lambda^{+}E=\\{\lambda(a)~{}|~{}(\exists s\in S(s_{0}))s\cdot a\in S\\}.$

Simplices are finite sets $\\{\lambda(a_{1}),\ldots,\lambda(a_{k})\\}$,
$k\geqslant 1$, for which the following two conditions hold:

  * •

$(a_{i},a_{j})\in I$, for all $1\leqslant i<j\leqslant k$;

  * •

there are $s\in S(s_{0})$ for which $s\cdot a_{1}\cdots a_{k}\in S$.

###### Remark 3.1

  1. (i)

For every $(s,a_{1},\ldots,a_{k})\in Q_{k}({\mathcal{A}})$, we include the set
$\\{\lambda(a_{1}),\ldots,\lambda(a_{k})\\}\\}$ in ${\mathfrak{M}}$.

  2. (ii)

If the elements are duplicated in
$\\{\lambda(a_{1}),\ldots,\lambda(a_{k})\\}$, then we remove them. For example
$\\{a,b,a,c,a,b\\}=\\{a,b,c\\}$.

###### Definition 3.2

Homology groups $H_{n}({\mathcal{A}},\lambda,L)$ of a labelled asynchronous
system is the homology groups $H_{n}(\lambda^{+}E,{\mathfrak{M}})$ of the
constructed simplicial scheme.

###### Example 3.3

Consider an asynchronous system ${\mathcal{A}}=(S,s_{0},E,I,{\rm Tran})$ where
$S=\\{000,001,010,011,100,101,110\\}$, $s_{0}=000$,
$E=\\{a_{1},a_{2},a_{3}\\}$,
$I=\\{(a_{1},a_{2}),(a_{2},a_{1}),(a_{1},a_{3}),(a_{3},a_{1}),(a_{2},a_{3}),(a_{3},a_{2})\\}$.
Transitions correspond to arrows of the diagram:

---
$\textstyle{001\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{2}}$$\textstyle{101}$$\textstyle{000\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{3}}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{2}}$$\textstyle{011}$$\textstyle{100\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{3}}$$\scriptstyle{a_{2}}$$\textstyle{010\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{3}}$$\scriptstyle{a_{1}}$$\textstyle{110}$

Let $L=E$ and let the label function $\lambda:E\to L$ is defined as
$\lambda(a)=a$ for all $a\in E$. The simplicial scheme consists of vertices
$E=\\{a_{1},a_{2},a_{3}\\}$ and simplices $\\{a_{1},a_{2}\\}$,
$\\{a_{1},a_{3}\\}$, $\\{a_{2},a_{3}\\}$. Define the order on vertices by
$a_{1}<a_{2}<a_{3}$. Homology groups is computed by the complex

$0\leftarrow{\,\mathbb{Z}}\\{a_{1},a_{2},a_{3}\\}\stackrel{{\scriptstyle
d_{1}}}{{\leftarrow}}{\,\mathbb{Z}}\\{(a_{1},a_{2}),(a_{1},a_{3}),(a_{2},a_{3})\\}\leftarrow
0$

Matrix for $d_{1}$ equals

$\displaystyle\quad\begin{array}[]{cccc}&~{}~{}~{}~{}(a_{1},a_{2})&~{}~{}~{}(a_{1},a_{3})&~{}~{}(a_{2},a_{3})\end{array}$
$\displaystyle\begin{array}[]{l}a_{1}\\\ a_{2}\\\
a_{3}\end{array}\quad\left(\begin{array}[]{ccc}~{}~{}~{}-1&~{}~{}~{}~{}~{}~{}~{}-1&~{}~{}~{}~{}~{}~{}~{}0\\\
~{}~{}~{}~{}1&~{}~{}~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}-1\\\
~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}~{}~{}1&~{}~{}~{}~{}~{}~{}~{}1\end{array}\quad\right)$

The Smith normal form for $d_{1}$ equals

$\displaystyle\quad\begin{array}[]{cccc}&~{}~{}~{}~{}(a_{1},a_{2})&~{}~{}~{}(a_{1},a_{3})&~{}~{}(a_{2},a_{3})\end{array}$
$\displaystyle\begin{array}[]{l}a_{1}\\\ a_{2}\\\
a_{3}\end{array}\quad\left(\begin{array}[]{ccc}~{}~{}~{}~{}1&~{}~{}~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}~{}0\\\
~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}~{}~{}1&~{}~{}~{}~{}~{}~{}~{}0\\\
~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}~{}0\end{array}\quad\right)$

It follows that
$H_{0}({\mathcal{A}},\lambda,L)={\,\mathbb{Z}}^{3-0-2}\oplus{\,\mathbb{Z}}/1{\,\mathbb{Z}}\oplus{\,\mathbb{Z}}/1{\,\mathbb{Z}}\cong{\,\mathbb{Z}}$,
$H_{1}({\mathcal{A}},\lambda,L)={\,\mathbb{Z}}^{3-2-0}\cong{\,\mathbb{Z}}$.
Other homology groups equal $0$.

The complex for computing groups $H_{n}({\mathcal{A}}(s),\lambda,L)$ for
$s=001$ has unique non-zero term ${\,\mathbb{Z}}\\{a_{1},a_{2}\\}$. It follows

$H_{n}({\mathcal{A}}(s),\lambda,L)=\left\\{\begin{array}[]{cl}{\,\mathbb{Z}}\oplus{\,\mathbb{Z}},&\mbox{
if }n=0,\\\ 0,&\mbox{ if }n>0.\\\ \end{array}\right.$

The complex for computing $H_{n}({\mathcal{A}}(s),\lambda,L)$ for $s=011$
consists of zeros. Therefore $H_{n}({\mathcal{A}}(011),\lambda,L)=0$ for all
$n\geqslant 0$.

###### Theorem 3.1

If labelled asynchronous systems $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ are $Pom_{L}$-bisimilar, then
their homology groups are isomorphic.

Proof. Denote by $\mathfrak{M}$ and $\mathfrak{M^{\prime}}$ the simplicial
schemes corresponded to the labelled asynchronous systems. If the labelled
asynchronous systems are $Pom_{L}$-bisimilar, then there is a labelled
asynchronous system together with the morphisms

$({\mathcal{A}},\lambda,L)\stackrel{{\scriptstyle(\sigma,\eta)}}{{\longleftarrow}}({\mathcal{A}}^{\prime\prime},\lambda^{\prime\prime},L)\stackrel{{\scriptstyle(\sigma^{\prime},\eta^{\prime})}}{{\longrightarrow}}({\mathcal{A}}^{\prime},\lambda^{\prime},L)~{}.$

Let $P^{f}(L)$ be the set of all finite subsets of $L$. Consider a maps
$\lambda_{n}:Q_{n}({\mathcal{A}})\to P^{f}(L)$ acting as
$\lambda(s,a_{1},\ldots,a_{n})=\\{\lambda(a_{1}),\ldots,\lambda(a_{n})\\}$.
The function $\lambda$ can have equal values. Hence, the set
$\\{\lambda(a_{1}),\ldots,\lambda(a_{n})\\}$ can contain $<n$ elements

For $n=0$, we let $\lambda_{0}(s)=\emptyset$. By Proposition 2.5 the maps
$Q_{n}(\sigma,\eta)$ and $Q_{n}(\sigma^{\prime},\eta^{\prime})$ are
surjective. The pairs $(\sigma,\eta)$ and $(\sigma^{\prime},\eta^{\prime})$
are morphisms of asynchronous systems. Hence, the following diagram is
commutative

---
$\textstyle{Q_{n}({\mathcal{A}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda_{n}}$$\textstyle{Q_{n}({\mathcal{A}}^{\prime\prime})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda_{n}^{\prime\prime}}$$\scriptstyle{Q_{n}(\sigma,\eta)}$$\scriptstyle{Q_{n}(\sigma^{\prime},\eta^{\prime})}$$\textstyle{Q_{n}({\mathcal{A}}^{\prime})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda^{\prime}_{n}}$$\textstyle{P^{f}(L)}$

We have the equalities
$Im(\lambda_{n})=Im(\lambda^{\prime\prime}_{n})=Im(\lambda^{\prime}_{n}).$
Consequently the simplicial sets $\mathfrak{M}$ and $\mathfrak{M^{\prime}}$
are equal. Therefore, the groups $H_{n}(\mathfrak{M})$ and
$H_{n}(\mathfrak{M^{\prime}})$ are isomorphic. $\Box$

###### Corollary 3.2

Let $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ be $Pom_{L}$-bisimilar
asynchronous systems. For each $w=a_{1}\cdots a_{k}\in E^{*}$, $k\geqslant 0$,
satifying $s_{0}\cdot w\in S$ there is a word $w^{\prime}=a^{\prime}_{1}\cdots
a^{\prime}_{k}\in E^{\prime*}$ such that $s^{\prime}_{0}\cdot w^{\prime}\in
S^{\prime}$ and

$(\forall n\geqslant 0)~{}H_{n}({\mathcal{A}}(s_{0}\cdot w),\lambda,L)\cong
H_{n}({\mathcal{A}}^{\prime}(s^{\prime}_{0}\cdot
w^{\prime}),\lambda^{\prime},L).$ (1)

Proof. By Proposition 2.3, in this case for the word $w$, there exists
$w^{\prime}$ for which $({\mathcal{A}}(s_{0}\cdot w),\lambda,L)$ and
$({\mathcal{A}}^{\prime}(s^{\prime}_{0}\cdot w^{\prime}),\lambda^{\prime},L)$
are $Pom_{L}$-bisimilar. Application of Theorem 3.1 to the obtained labelled
asynchronous systems leads us to desired isomorphism of the homology groups.
$\Box$

###### Example 3.4

Consider well known labelled asynchronous systems

$\textstyle{s_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{2}}$$\textstyle{s_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\textstyle{s_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{c}$$\textstyle{s_{3}}$$\textstyle{s_{4}}$
$\textstyle{s_{0}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\textstyle{s_{1}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\scriptstyle{c}$$\textstyle{s_{2}^{\prime}}$$\textstyle{s_{3}^{\prime}}$

The first asynchronous system ${\mathcal{A}}$ consists of
$S=\\{s_{0},s_{1},s_{2},s_{3},s_{4}\\}$, $E=\\{a_{1},a_{2},b,c\\}$,
$I=\emptyset$, ${\rm
Tran}=\\{(s_{0},a_{1},s_{1}),(s_{0},a_{2},s_{2}),(s_{1},b,s_{3}),(s_{2},c,s_{4})\\}$.

The second asynchronous system ${\mathcal{A}}^{\prime}$ consists of
$S^{\prime}=\\{s^{\prime}_{0},s^{\prime}_{1},s^{\prime}_{2},s^{\prime}_{3}\\}$,
$E^{\prime}=\\{a,b,c\\}$, $I^{\prime}=\emptyset$, ${\rm
Tran}=\\{(s^{\prime}_{0},a,s^{\prime}_{1}),(s^{\prime}_{1},b,s^{\prime}_{2}),(s^{\prime}_{1},c,s^{\prime}_{3})\\}$.

The label functions have values in $L=\\{a,b,c\\}$ and are defined by

$\lambda(a_{1})=\lambda(a_{2})=\lambda^{\prime}(a)=a,~{}\lambda(b)=\lambda^{\prime}(b)=b,~{}\lambda(c)=\lambda^{\prime}(c)=c.$

Compute $H_{n}({\mathcal{A}}(s_{1}),\lambda,L)$ by the complex
$0\leftarrow{\,\mathbb{Z}}\\{b\\}\leftarrow 0$. We have

$H_{n}({\mathcal{A}}(s_{1}),\lambda,L)=\left\\{\begin{array}[]{cl}{\,\mathbb{Z}},&\mbox{
if }n=0,\\\ 0,&\mbox{ if }n>0.\\\ \end{array}\right.$

The groups $H_{n}({\mathcal{A}}^{\prime}(s_{1}^{\prime}),\lambda^{\prime},L)$
are isomorphic to homology groups of the complex
$0\leftarrow{\,\mathbb{Z}}\\{b\\}\oplus{\,\mathbb{Z}}\\{c\\}\leftarrow 0$. We
have

$H_{n}({\mathcal{A}}^{\prime}(s_{1}^{\prime}),\lambda^{\prime},L)=\left\\{\begin{array}[]{cl}{\,\mathbb{Z}}\oplus{\,\mathbb{Z}},&\mbox{
if }n=0,\\\ 0,&\mbox{ if }n>0.\\\ \end{array}\right.$

The groups $H_{0}({\mathcal{A}}(s_{1}),\lambda,L)$ and
$H_{0}({\mathcal{A}}^{\prime}(s_{1}^{\prime}),\lambda^{\prime},L)$ are not
isomorphic. It follows from Corollary 3.2 that $({\mathcal{A}},\lambda,L)$ and
$({\mathcal{A}}^{\prime},\lambda^{\prime},L)$ are not $Pom_{L}$-bisimilar.

##  4 Homology groups of labelled Petri nets

Recall some definitions from theory of Petri nets. Then consider homology
groups of labelled Petri nets and prove that for each simplicial scheme, there
is a labelled Petri net homological equivalent to this simplicial scheme.

###  4.1 Petri nets

We view “display” and “function” as synonyms. For a finite set $P$, let
${\,\mathbb{N}}^{P}$ denotes a set of all functions $M:P\to{\,\mathbb{N}}$,
where ${\,\mathbb{N}}=\\{0,1,2,\ldots\\}$ is the set of non-neganbve integers.
For any $M_{1},M_{2}\in{\,\mathbb{N}}^{P}$, define a sum $M_{1}+M_{2}$ as a
function with values $(M_{1}+M_{2})(p)=M_{1}(p)+M_{2}(p)$ for all $p\in P$.
Let $M_{1}\geqslant M_{2}$ if $M_{1}(p)\geqslant M_{2}(p)$ for all $p\in P$.
If $M_{1}\geqslant M_{2}$, then we can define a difference $M_{1}-M_{2}$ as
the function with the values $M_{1}(p)-M_{2}(p)$. Define a scalar product by
$M_{1}\cdot M_{2}=\sum_{p\in P}M_{1}(p)M_{2}(p)$.

A Petri net ${\,\cal N}=(P,T,pre,post,M_{0})$ consists of finite sets $P$ and
$T$ with two maps $pre:T\to{\,\mathbb{N}}^{P}$, $post:T\to{\,\mathbb{N}}^{P}$
and a function $M_{0}:P\to{\,\mathbb{N}}$ called initial marking. Elements
$p\in P$ are called places, and $t\in T$ are events. A marking is an arbitrary
function $M:P\to{\,\mathbb{N}}$.

$t_{1}$$t_{2}$$t_{3}$$p_{2}$$p_{1}$ Figure 4: Example of Petri net

A Petri net can be given as a directed graph whose vertices are places
depicted by circles, and events depicted by rectangles. Every arrow goes from
an event to a place or from a place to an event. For any $t\in T$, the number
entering into it arrows equals $pre(t)(p)$ and the number of arrows outgoing
from $t$ equals $post(t)(p)$. The initial marking is given by drawing the
points in each place. These points are called tokens. The number of tokens in
a place $p$ is equal to $M_{0}(p)$. If $M_{0}(p)=0$, then the place is empty.

Fig. 4 shows a Petri net ${\,\cal N}=(P,T,pre,post,M_{0})$ where
$P=\\{p_{1},p_{2}\\}$, $T=\\{t_{1},t_{2},t_{3}\\}$. The values
$pre(t_{i})(p_{j})$ and $post(t_{i})(p_{j})$, $1\leqslant i\leqslant 3$,
$1\leqslant j\leqslant 2$, are equal to the entries of the matrices

$(pre(t_{i})(p_{j}))=\left(\begin{array}[]{cc}0&0\\\ 1&1\\\
0&1\end{array}\right)\qquad(post(t_{i})(p_{j}))=\left(\begin{array}[]{cc}2&1\\\
0&0\\\ 0&0\end{array}\right)$

###  4.2 Labelled asynchronous system for a Petri net and its homology groups

Let ${\,\cal N}=(P,T,pre,post,M_{0})$ be a Petri net. Consider a corresponding
asynchronous system ${\mathcal{A}}({\,\cal N})=(S,s_{0},E,I,{\rm Tran})$, with
$S={\,\mathbb{N}}^{P}$, $s_{0}=M_{0}$, $E=T$. The relation of independence $I$
consists of pairs $(e_{1},e_{2})\in T\times T$ for which the scalar product
$(pre(e_{1})+post(e_{1})\cdot(pre(e_{2})+post(e_{2}))$ equals $0$. This means
that $e_{1}$ and $e_{2}$ do not have common input or output places. The set
${\rm Tran}$ consists of triples $(M,e,M^{\prime})$ where $M$ and $M^{\prime}$
are markings and $e\in T$ satifies two following conditions

  * •

$M\geqslant pre(e)$,

  * •

$M-pre(e)+post(e)=M^{\prime}$.

If $(M,e,M^{\prime})\in{\rm Tran}$, then we say that the marking $M^{\prime}$
is obtained from $M$ by operation of event $e\in T$. For example, for Petri
net in Fig. 4, we have $pre(t_{2})\geqslant M_{0}$. The operation of the event
$t_{2}$ leads to the new magking $M_{1}=M_{0}-pre(t_{2})+post(t_{2})$ (Fig.
5).

$t_{1}$$t_{2}$$t_{3}$$p_{2}$$p_{1}$ Figure 5: The marking obtained by
operation of the event $t_{2}$

Let $L$ be an arbitrary nonempty set. A Petri net ${\,\cal N}$ with a function
$\lambda:T\to L$ is called labelled. The asynchronous system
${\mathcal{A}}({\,\cal N})$ corresponding ${\mathcal{A}}$ has the set of
events $E=T$. Hence, for any labelled Petri nets, it is defined the labelled
asynchronous system $({\mathcal{A}}({\,\cal N}),\lambda,L)$.

###### Definition 4.1

Let $({\,\cal N},\lambda,L)$ be a labelled Petri net. Its homology groups
$H_{n}({\,\cal N},\lambda,L)$ are defined as $H_{n}({\mathcal{A}}({\,\cal
N}),\lambda,L)$, $n\geqslant 0$.

###### Example 4.2

Consider the Petri net ${\,\cal N}=(P,T,pre,post,M_{0})$, in Fig. 6. Let
$L=E=\\{t_{1},t_{2},t_{3},t_{4}\\}$, $\lambda(t_{i})=i$, for all $1\leqslant
i\leqslant 4$.

$\textstyle{t_{1}}$$\textstyle{\bigodot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces~{}p_{1}}$$\textstyle{p_{3}~{}\bigodot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{t_{3}}$$\textstyle{t_{2}}$$\textstyle{\bigodot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces~{}p_{2}}$$\textstyle{p_{4}~{}\bigodot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{t_{4}}$
Figure 6: Example of computing the homology groups of Petri net

The relation $I$ contains the pairs $(t_{1},t_{3})$, $(t_{1},t_{4})$,
$(t_{2},t_{3})$, $(t_{2},t_{4})\\}$, $(t_{3},t_{1})$, $(t_{3},t_{2})$,
$(t_{4},t_{1})$, $(t_{4},t_{2})$. The simplicial set $(E,{\mathfrak{M}})$ give
the following sets of simplices

${\mathfrak{M}}_{0}=\\{t_{1},t_{2},t_{3},t_{4}\\},\\\
{\mathfrak{M}}_{1}=\\{(t_{1},t_{3}),(t_{1},t_{4}),(t_{2},t_{3}),(t_{2},t_{4})\\},~{}$

and ${\mathfrak{M}}_{n}=\emptyset$ for $n\geqslant 2$. We get the following
complex for the computing the homology groups of the labelled Petri nets:

$0\leftarrow{\,\mathbb{Z}}^{4}\stackrel{{\scriptstyle
d_{1}}}{{\longleftarrow}}{\,\mathbb{Z}}^{4}\leftarrow 0.$

The differential $d_{1}$ is given by the matrix

$\displaystyle\quad\begin{array}[]{cccccc}&~{}~{}(t_{1},t_{3})&(t_{1},t_{4})&(t_{2},t_{3})&(t_{2},t_{4})\end{array}$
$\displaystyle\begin{array}[]{l}t_{1}\\\ t_{2}\\\ t_{3}\\\
t_{4}\end{array}\left(\begin{array}[]{cccc}-1&~{}~{}~{}~{}~{}-1&~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}~{}0\\\
~{}0&~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}-1&~{}~{}~{}~{}~{}-1\\\
+1&~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}+1&~{}~{}~{}~{}~{}~{}0\\\
~{}0&~{}~{}~{}~{}~{}+1&~{}~{}~{}~{}~{}~{}0&~{}~{}~{}~{}~{}+1\end{array}\right)$

Its Smith normal form has the diagonal entries $(1,1,1,0)$. Consequently

$H_{0}({\,\cal N},\lambda,L)\cong H_{1}({\,\cal
N},\lambda,L)={\,\mathbb{Z}}\mbox{ and }H_{n}({\,\cal N},\lambda,L)=0\mbox{
for all }n\geqslant 2.$

A sequence of Abelian groups $A_{k}$, $k\geqslant 0$, is called to be finite
if there is $n\geqslant 0$ such that $A_{k}=0$ for all $k>n$.

###### Theorem 4.1

For an arbitrary finite sequence of finitely generated Abelian groups $A_{0}$,
$A_{1}$, $A_{2}$, …where $A_{0}$ is free and is not equal to $0$, there exists
a labelled Petri net such that its $k$th homology groups are isomorphic to
$A_{k}$ for all $k\geqslant 0$.

Proof. In this case by [17, Chapter 4, Exercise C-7], there exists a compact
polyhedron with homology groups $A_{k}$ for all $k\geqslant 0$. Compact
polyhedra are precisely the topological spaces admitting triangulations [17,
Chapter 3, Corollary 20]. Hence, there exists a simplicial scheme
$(X,{\mathfrak{M}})$ the homology groups of which are isomorphic to $A_{k}$.

Let $(E,{\mathfrak{M}}^{\prime})$ be a barycentric subdivision of the
simplicial set $(E,{\mathfrak{M}})$. Vertices $e\in E$ of the barycentric
subdivision are simplices $\sigma\in{\mathfrak{M}}$. Simplices of
$(E,{\mathfrak{M}}^{\prime})$ are finite sets of simplices
$\\{\sigma_{0},\ldots,\sigma_{n}\\}$ totally ordered by the relation
$\subseteq$. It means that there is a permutation
$(\sigma_{i_{0}},\ldots,\sigma_{i_{n}})$ such that
$\sigma_{i_{0}}\subset\sigma_{i_{1}}\subset\ldots\subset\sigma_{i_{n}}$. It is
well known that homology groups of $(E,{\mathfrak{M}}^{\prime})$ are
isomorphic to homology groups of $(X,{\mathfrak{M}})$. Define a relation $I$
on $E$ by

$(\sigma,\sigma^{\prime})\in
I\Leftrightarrow\sigma\subset\sigma^{\prime}\vee\sigma^{\prime}\subset\sigma.$

$p_{1}$$p_{2}$$p_{m}$$e_{1}$$e_{2}$$e_{m}$ Figure 7: The constructing of a
Petri net

Building a Petri net is similar to the construction of the work [18]. Denote
the elements of $E$ by $e_{1}$, $e_{2}$, …, $e_{m}$ where $m=|E|$. Consider
the Petri net depicted in Fig. 7. It consists of places $p_{i}$, connected
with the events $e_{i}$ by the arrows where $i=1,2,\ldots,m$. The initial
marking is defined as $M_{0}(p_{i})=1$ for all $i=1,2,\ldots,e_{m}$. For every
$(e_{i},e_{j})\notin I$, we make the events $e_{i}$ and $e_{j}$ to be
dependent by adding two arrows as shown in Fig. 8.

$p_{i}$$p_{j}$$e_{i}$$e_{j}$ Figure 8: Adding arrows to the Petri net

Let $L=E$ and let the label function defined as $\lambda(e_{i})=e_{i}$ for all
$i=1,\ldots,m$. For every $e_{i}\in E$, we have $s_{0}\cdot e_{i}\in S$. It
follows that the set of vertices of a simplicial scheme corresponding to the
Petri net is equal to $E$. For each nonempty subset
$\\{e_{i_{0}},\ldots,e_{i_{n}}\\}\subseteq E$ consisting of mutually
independent elements, we have $s_{0}\cdot e_{i_{0}}\cdots e_{i_{n}}\in S$.
Consequently the simplicial set corresponding to the Petri net is equal to
$(E,{\mathfrak{M}}^{\prime})$. Thus, $H_{n}({\,\cal N},\lambda,L)=A_{n}$ for
all $n\geqslant 0$. $\Box$

###### Corollary 4.2

For any finite sequence of finitely generated Abelian groups $A_{0}$, $A_{1}$,
$A_{2}$, …where $A_{0}$ is free and non-zero, there is a labelled asynchronous
system the $k$th homology groups of which are isomorphic to $A_{k}$ for all
$k\geqslant 0$.

## References

  * [1] A. Joyal, M. Nielsen and G. Winskel, Bisimulation from open maps, LICS93 BRICS Report RS-94-7, Aarhus Univ., 1994. 42 pp.
  * [2] R. Milner, Communication and concurrency. International Series in Computer Science (Prentice Hall, New York, 1989).
  * [3] M. Nielsen and G. Winskel, Petri nets and bisimulation, Theoret. Comput. Sci., 153:1-2 (1996) 211–244.
  * [4] M. Herlihy and N. Shavit, The Topological Structure of Asynchronous Computability, Journal of ACM, 46:6 (1999) 858–923.
  * [5] E. Goubault and T.P. Jensen, Homology of higher dimensional automata, Lecture Notes in Computer Science, Vol. 630, (Springer, Berlin, 1992) 254–268.
  * [6] E. Goubault, The Geometry of Concurrency,  Ph.D. Thesis, Ecole Normale Supérieure, 1995, 349 p.
  * [7] L. Fajstrup, M. Raußen, E.Goubault. Algebraic topology and concurrency, Theoret. Comput. Sci. 357:1-3 (2006) 241–278.
  * [8] E. Goubault, E. Haucourt and S. Krishnan, Covering space theory for directed topology, Theor. Appl. Categ. 22:9 (2009) 252–268.
  * [9] U. Fahrenberg, A. Legay, History-Preserving Bisimilarity for Higher-Dimensional Automata via Open Maps, arXiv:1209.4927v2 [cs.LO], (Cornell Ubiversity, New York, 2012).
  * [10] A. Husainov, On the homology of small categories and asynchronous transition systems, Homology Homotopy Appl., 6:1 (2004) 439–471.
  * [11] A. A. Khusainov, V. E. Lopatkin, I. A. Treshchev, Studying a mathematical model of parallel computation by algebraic topology methods, Journal of Applied and Industrial Math. 3:3 (2009) 353-363.
  * [12] A. A. Husainov, The cubical homology of trace monoids, Far Eastern Math. Journal 12:1 (2012) 108–122
http://mi.mathnet.ru/eng/dvmg/v12/i1/p108

  * [13] A. A. Husainov, The Homology of Partial Monoid Actions and Petri Nets, Appl. Categor. Struct. (2012) DOI: 10.1007/s10485-012-9280-9.
  * [14] G. Winskel and M. Nielsen, Models for Concurrency, in: Abramsky, Gabbay and Maibaum, eds., Handbook of Logic in Computer Science, Vol.4 (Oxford University Press, Oxford, 1995) 1–148.
  * [15] M. A. Bednarczyk, Categories of Asynchronous Systems, Ph.D. thesis, University of Sussex, Report No. 1/88, 1988.
  * [16] V. Diekert, Y. Métivier, Partial Commutation and Traces, in: Handbook of formal languages, Vol. 3, ( Springer, New York, 1997) 457–533.
  * [17] E.H. Spanier, Algebraic topology, (McGraw-Hill Book Company, New York, 1966).
  * [18] A. A. Khusainov, Homology groups of asynchronous systems, Petri nets, and trace languages, Sib. Electron. Mat. Izv., 2012. v. 9. P. 13-44. (Russian)