# Category of asynchronous systems and polygonal morphisms

A. A. Husainov<EMAIL_ADDRESS>
###### Abstract

A weak asynchronous system is a trace monoid with a partial action on a set. A
polygonal morphism between weak asynchronous systems commutes with the actions
and preserves the independence of events. We prove that the category of weak
asynchronous systems and polygonal morphisms has all limits and colimits.

2010 Mathematics Subject Classification 18A35, 18A40, 18B20, 68Q85

Keywords: trace monoid, partial monoid action, limits, colimits, asynchronous
transition system.

## Introduction

Mathematical models of parallel systems find numerous applications in parallel
programming. They are applied for the development and verification of
programs, for searching deadlocks and estimation of runtime. These models are
widely applied to the description of semantics and the development of
languages of parallel programming [17].

There are various models of parallel computing systems [18]. For example, for
the solution of the dining philosophers problem, it is convenient to use
higher dimensional automata [7], but for a readers/writers problem, it is
better to consider asynchronous systems [12]. For comparing the models, the
adjoint functors between categories of these models are constructed [9], [10],
[11], [19].

But, at comparision of asynchronous transition systems and higher dimensional
automata, we face the open problem, whether there are colimits in the category
of asynchronous systems. We propose avoid this obstacle by constructing a
cocomplete category of asynchronous systems, and it allows us to build adjoint
functors in the standard way.

The asynchronous system is a model of the computing system consisting of
events (instructions, machine commands) and states. The states are defined by
values of variables (or cells of memory). Some events can occur
simultaneously. The category of asynchronous systems for the first time has
been studied by M. Bednarczyk [1]. Class of morphisms was extended in [2].

We consider asynchronous system as set with partial trace monoid action. We
represent the action as total, adding to asynchronous system a state “at
infinity”. Morphisms between trace monoids acting on the pointed sets lead to
polygonal morphisms of weak asynchronous systems.

These morphisms have great value for studying homology groups of the
asynchronous systems, introduced in [12]. They also help in the studying
homology groups of the Mazurkiewicz trace languages and Petri nets [14]. The
review of the homology of asynchronous systems is contained in [13].

The paper consist of three sections. In the first, the category $FPCM$ of
trace monoids and basic homomorhisms is investigated. It is proved, that in
this category, there are limits (Theorem 1.6) and colimits (Theorem 1.8)
though even finite products do not coincide with Cartesian products. The
subcategory $FPCM^{\|}\subset FPCM$ with independence preserving morphisms is
studied. It is proved, that this subcategory is complete (Theorem 1.14) and
cocomplete (Theorem 1.15). In the second section, the conditions of existence
of limits and colimits in a category of diagrams over the fixed category are
studied. The third section is devoted to a category of weak asynchronous
systems and polygonal . Main results about completeness and cocompleteness of
a category of weak asynchronous systems and polygonal morphisms are proved
(Theorems 3.12 and 3.13).

##  1 Categories of trace monoids

Bases of the trace monoid theory have been laid in [4]. Applications in
computer science belong to A. Mazurkiewicz [16], V. Diekert, Y. Métivier [6].
We shall consider a trace monoid category and basic homomorphisms and its
subcategory consisting of independence preserving homomorphisms.

The diagram is functor defined on a small category. Our objective is research
of a question on existence of limits and colimits of diagrams in these
categories.

###  1.1 Trace monoids

A map $f:M\to M^{\prime}$ between monoids is homomorphism, if $f(1)=1$ and
$f(\mu_{1}\mu_{2})=f(\mu_{1}\mu_{2})$ for all $\mu_{1},\mu_{2}\in M$. Denote
by $Mon$ the category of all monoids and homomorphisms.

Let $E$ be an arbitrary set. An independence relation on $E$ is subset
$I\subseteq E\times E$ satisfying the following conditions:

  * •

$(\forall a\in E)~{}(a,a)\notin I$,

  * •

$(\forall a,b\in E)~{}(a,b)\in I\Rightarrow(b,a)\in I$.

Elements $a,b\in E$ are independent, if $(a,b)\in I$.

Let $E^{*}$ be the monoid of all words $a_{1}a_{2}\cdots a_{n}$ where
$a_{1},a_{2},\cdots,a_{n}\in E$ and $n\geqslant 0$, with operation of
concatenation

$(a_{1}\cdots a_{n})(b_{1}\cdots b_{m})=a_{1}\cdots a_{n}b_{1}\cdots b_{m}\,.$

The identity $1$ is the empty word.

Let $I$ be an independence relation on $E$. We define the equivalence relation
$\equiv_{I}$ on $E^{*}$ putting $w_{1}\equiv_{I}w_{2}$ if $w_{2}$ can be
receive from $w_{1}$ by a finite sequence of adjacent independent elements.

---
$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{e\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{c\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{d}$
Figure 1: Independence graph

For example, for the set $E=\\{a,b,c,d,e\\}$ and for the relation $I$ given by
the adjacency graph drawn in Figure 1 the sequence of permutations

$eadcc\stackrel{{\scriptstyle(e,a)}}{{\to}}aedcc\stackrel{{\scriptstyle(e,d)}}{{\to}}adecc\stackrel{{\scriptstyle(e,c)}}{{\to}}adcec\stackrel{{\scriptstyle(d,c)}}{{\to}}acdec\stackrel{{\scriptstyle(e,c)}}{{\to}}acdce\stackrel{{\scriptstyle(d,c)}}{{\to}}accde$

shows that $adecc\equiv_{I}accde$.

For every $w\in E^{*}$, its equivalence class $[w]$ is called the trace.

###### Definition 1.1

Let $E$ be a set and let $I$ be an independence relation. A trace monoid
$M(E,I)$ is the set of equivalence classes $[w]$ of all $w\in E^{*}$ with the
operation $[w_{1}][w_{2}]=[w_{1}w_{2}]$ for $w_{1},w_{2}\in E^{*}$.

We emphasize that the set $E$ can be infinite.

In some cases, we omit the square brackets in the notations for elements of
$M(E,I)$. If $I=\emptyset$, then $M(E,I)$ is equal to the free monoid $E^{*}$.
If $I=((E\times E)\setminus\\{(a,a)|a\in E\\})$, then $M(E,I)$ is the free
commutative monoid. In this case, we denote it by $M(E)$.

###  1.2 The category of trace monoids and basic homomorphisms

Let us introduce basic homomorphisms and we shall show, that the category of
trace monoids and basic homomorphism is complete and cocomplete.

###### Definition 1.2

A homomorphism $f:M(E,I)\to M(E^{\prime},I^{\prime})$ is basic if
$f(E)\subseteq E^{\prime}\cup\\{1\\}$.

If $w=e_{1}\cdots e_{n}\in M(E,I)$ for some $e_{1}\in E$, …, $e_{n}\in E$,
then $n$ is called the length of the trace $w$. It is easy to see, that a
homomorphism will be basic, if and only if it does not increase length of
elements of $M(E,I)$. Let $FPCM$ be a category of trace monoids and basic
homomorphisms.

Consider the problem on existence of the products in $FPCM$. The Cartesian
product $M(E_{1},I_{1})\times M(E_{2},I_{2})$ will not be the product in
$FPCM$. Thus for building products and other constructions, we shall consider
partial maps as total, adding to them the element $*$.

Let $E_{*}=E\sqcup\\{*\\}$. We assign to each partial map
$f:E_{1}{\rightharpoonup}E_{2}$, a total map $f_{*}:{E_{1}}_{*}\to{E_{2}}_{*}$
defined as

$f_{*}(a)=\left\\{\begin{array}[]{cc}f(a),&\mbox{ if }f(a)\mbox{ defined},\\\
,&\mbox{ otherwise.}\end{array}\right.$

Any basic homomorphism $M(E_{1},I_{1})\to M(E_{2},I_{2})$ can be given by some
partial map $f:E_{1}{\rightharpoonup}E_{2}$. We consider it as the pointed
total map $f_{*}:{E_{1}}_{*}\to{E_{2}}_{*}$ which brings any pair $(a,b)\in
I_{1}\cup(E_{1}\times\\{*\\})\cup(\\{*\\}\times E_{1})$ to the pair
$(f_{*}(a),f_{*}(b))\in I_{2}\cup(E_{2}\times\\{*\\})\cup(\\{*\\}\times
E_{2})$. It is clear that $f_{*}$ bring the elements of
$\Delta_{{E_{1}}_{*}}=\\{(a,a)|a\in{E_{1}}_{*}\\}$ to
$(f_{*}(a),f_{*}(a))\in\Delta_{{E_{2}}_{*}}$.

Let $ComRel$ be the category of pairs $(E_{*},T)$ where each pair consists of
a pointed set $E_{*}$ and binary relation of commutativity $T\subseteq
E_{*}\times E_{*}$ satisfying the following conditions

  1. (i)

$(\forall a\in E_{*})~{}(a,*)\in T~{}\&~{}(*,a)\in T$ (commutativity with
$1$),

  2. (ii)

$(\forall a\in E_{*})~{}(a,a)\in T$ (reflexivity),

  3. (iii)

$(\forall a,b\in E_{*})(a,b)\in T\Rightarrow(b,a)\in T$ (symmetry).

Morphisms $({E_{1}}_{*},T_{1})\stackrel{{\scriptstyle
f}}{{\to}}({E_{2}}_{*},T_{2})$ in the category $ComRel$ are poinded maps
$f:{E_{1}}_{*}\to{E_{2}}_{*}$ satisfying $(a_{1},b_{1})\in
T_{1}\Rightarrow(f(a_{1}),f(b_{1}))\in T_{2}$.

###### Proposition 1.3

The category $FPCM$ is isomorphic to $ComRel$.

Proof. Define the functor $FPCM\to ComRel$ on objects by
$M(E,I)\mapsto(E_{*},T)$ where $T=I\cup(E\times\\{*\\})\cup(\\{*\\}\times
E)\cup\Delta_{E_{*}}$. The functor transforms basic homomorphisms
$f:M(E_{1},I_{1})\to M(E_{2},I_{2})$ into the maps
$f_{*}:{E_{1}}_{*}\to{E_{2}}_{*}$ assigning to pairs $(a_{1},b_{1})\in T_{1}$
the pairs $(f_{*}(a_{1}),f_{*}(b_{1}))\in T_{2}$.

An inverse functor assigns to each object $(E_{*},T)$ of the category $ComRel$
the trace monoid $M(E,I)$, where

$I=T\setminus\left(\\{(a,a)|a\in E_{*}\\}\cup\\{(a,*)|a\in
E\\}\cup\\{(*,a)|a\in E\\}\right),$ (1)

and to any morhism $({E_{1}}_{*},T_{1})\stackrel{{\scriptstyle
f}}{{\to}}({E_{2}}_{*},T_{2})$ the homomorphism
$\widetilde{f}:M(E_{1},I_{1})\to M(E_{2},I_{2})$ given at basic elements as
$\widetilde{f}(e)=f(e)$ if $f(e)\in E_{2}$, and $\widetilde{f}(e)=1$, if
$f(e)=*$. $\Box$

Consider a family of trace monoids $\\{M(E_{j},I_{j})\\}_{j\in J}$. Transform
it to family of pointed sets with commutativity relations
$\\{({E_{j}}_{*},T_{j})\\}_{j\in J}$. The product of this family in the
category $ComRel$ equals the Cartesian product $(\prod\limits_{j\in
J}{E_{j}}_{*},\prod\limits_{j\in J}T_{j})$. The category $FPCM$ is isomorphic
to $ComRel$. Therefore, we obtain the following

###### Proposition 1.4

The category $FPCM$ has the products.

Any object $(E_{*},T)$ of $ComRel$ corresponds to a trace monoid $M(E,I)$ with
the set $E=E_{*}\setminus\\{*\\}$ and independence relation defined by formula
(1).

It follows that the product of $M(E_{j},I_{j})$, $j\in J$ has the set of
generators $E=(\prod\limits_{j\in J}E_{j*})\setminus\\{(*)\\}$ where
$(*)\in\prod\limits_{j\in J}E_{j*}$ denotes a family of elements each of which
equals $*\in{E_{j}}_{*}$. Let

$T_{j}=I_{j}\cup(\\{(a,a)|a\in{E_{j}}_{*}\\}\cup\\{(a,*)|a\in
E_{j}\\}\cup\\{(*,a)|a\in E_{j}\\}).$

The relation $I$ is received from $T=\prod\limits_{j\in J}T_{j}$ by the
formula (1).

###### Example 1.5

Let $J=\\{1,2\\}$, $E_{1}=\\{e_{1}\\},E_{2}=\\{e_{2}\\}$,
$I_{1}=I_{2}=\emptyset$. Then $M(E_{1},I_{1})\cong
M(E_{2},I_{2})\cong{\,\mathbb{N}}$ are isomorphic to the monoid generated by
one element. Compute $M(E,I)=M(E_{1},I_{1})\prod M(E_{2},I_{2})$. The set
$E_{*}$ equals ${E_{1}}_{*}\times{E_{2}}_{*}$. In following picture at the
left, it is shown the graph of the relation $T\subseteq E_{*}\times E_{*}$ and
on the right it is shown the graph of the relation $I$ obtained by the formula
(1).

$\textstyle{(*,*)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(e_{1},*)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(*,e_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(e_{1},e_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
$\textstyle{(e_{1},*)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(*,e_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(e_{1},e_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

We see, that the product is isomorphic to a free commutative monoid generated
by three elements.

###### Theorem 1.6

For each diagram $D$ in $FPCM$, there is the limit.

Proof. Since $FPCM$ has all products, it is enough existence of equalizers.
Consider a pair
$\textstyle{M(E_{1},I_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{M(E_{2},I_{2})}$
of basic homomorphisms. Let $E=\\{e\in E_{1}~{}|~{}f(e)=g(e)\\}$. The
submonoid of $M(E_{1},I_{1})$ generated by $E$ is a trace monoid $M(E,I)$ with
the independence relation $I=I_{1}\cap(E\times E)$. Consider an arbitrary
basic homomorphism $h^{\prime}:M(E^{\prime},I^{\prime})\to M(E_{1},I_{1})$
such that $g(h^{\prime}(e^{\prime}))=f(h^{\prime}(e^{\prime}))$ for all
$e^{\prime}\in E^{\prime}$. Obtain $h^{\prime}(e^{\prime})\in E\cup\\{1\\}$.
It follows that $h^{\prime}$ maps $M(E^{\prime},I^{\prime})$ into $M(E,I)$ and
the following triangle is commutative:

---
$\textstyle{M(E,I)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\subseteq}$$\textstyle{M(E_{1},I_{1})}$$\textstyle{M(E^{\prime},I^{\prime})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$

Therefore, the inclusion $M(E,I)$ into $M(E_{1},I_{1})$ is equalizer of the
pair $(f,g)$. $\Box$

###### Proposition 1.7

Let $\operatorname{{\rm Ob}}{Mon}\to\operatorname{{\rm Ob}}FPCM$ be the map
carried each monoid $M$ to a trace monoid $M(M\setminus\\{1\\},I_{M})$ with

$I_{M}=\\{(\mu_{1},\mu_{2})\in(M\setminus\\{1\\})\times(M\setminus\\{1\\})|~{}\mu_{1}\not=\mu_{2}~{}\&~{}\mu_{1}\mu_{2}=\mu_{2}\mu_{1}\\}.$

This map can be extended to a functor $R:{Mon}\to FPCM$ right adjoint to the
inclusion $U:FPCM\to{Mon}$.

Proof. Define a homomorphism $\varepsilon_{M}:M(M\setminus\\{1\\},I_{M})\to M$
setting $\varepsilon(\mu)=\mu$ on the generators of
$M(M\setminus\\{1\\},I_{M})\to M$. It easy to see that for each homomorphism
$f:M(E,I)\to M$, there exists unique basic homomorphism $\overline{f}$ making
the following diagram commutative

---
$\textstyle{M(M\setminus\\{1\\},I_{M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon_{M}}$$\textstyle{M}$$\textstyle{M(E,I)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{f}}$$\scriptstyle{f}$

It is defined by $\overline{f}(e)=f(e)$ on elements $e\in E$. This
homomorphism is couniversal arrow. By the universal property, the map
$M\mapsto(M(M\setminus\\{1\\},I_{M}),\varepsilon_{M})$ uniquely extends up to
the right adjoint functor. $\Box$

###### Theorem 1.8

The category $FPCM$ is cocomplete and the inclusion functor $FPCM$ into the
category ${Mon}$ preserves all colimits.

Proof. Let $D:J\to FPCM$ be a diagram with values $D(j)=M(E_{j},I_{j})$.
Consider $\underrightarrow{\lim}^{J}D$ in the category $Mon$ of all monoids.
The colimit is isomorphic to a quotient monoid $\coprod_{j\in
J}M(E_{j},I_{j})/\equiv$ obtained from the coproduct in $Mon$ by
identifications of elements $e_{j}\equiv D(j\to k)e_{j}$. It follows that the
colimit is generated by the disjoint union $\coprod\limits_{j\in J}E_{j}$ and
represented by the following equations:

  1. (i)

for all $j\in J$, $(e,e^{\prime})\in I_{j}$ it is true $ee^{\prime}\equiv
e^{\prime}e$,

  2. (ii)

if $e^{\prime}_{k}=D(j\to k)(e_{j})$ for some $e_{j}\in E_{j}$,
$e^{\prime}_{k}\in E_{k}$, then $e_{j}\equiv e^{\prime}_{k}$,

  3. (iii)

$e_{j}\equiv 1$ if $M(j\to k)(e_{j})=1$.

This monoid is generated by a set $E$ received of a quotient set of
$\coprod\limits_{j\in J}E_{j}$ under the equivalence relation containing pairs
type (ii) by removing the classes containing elements $e_{j}\equiv 1$. The
equations (i) give the relation $I$. We obtain the trace monoid
$\underrightarrow{\lim}^{J}D=M(E,I)$. The morphisms of colimiting cone are
basic homomorhisms sending to every $e_{j}$ its equivalence class or $1$. For
any other cone $f_{j}:M(E_{j},I_{j})\to M(E^{\prime},I^{\prime})$ consisting
of basic homomorphisms, the morphism $\underrightarrow{\lim}^{J}D\to
M(E^{\prime},I^{\prime})$ assigns to each class $[e_{j}]$ the element
$f_{j}(e_{j})$.

---
$\textstyle{M(E,I)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\textstyle{M(E_{j},I_{j})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda_{j}}$$\scriptstyle{f_{j}}$$\textstyle{M(E^{\prime},I^{\prime})}$

Therefore, $FPCM$ has all colimits.

It follows from 1.7 that the inclusion $FPCM\subset Mon$ preserves all
colimits as having right adjoint [15]. $\Box$

###### Example 1.9

Consider the free commutative monoid $M(\\{a,b\\})$ and the trace monoid
$M=M(\\{c,d,e\\},\\{(c,d),(d,c),(d,e),(e,d)\\})$. Let $f,g:M\\{a,b\\}\to M$ be
two homomorphisms defined as $f(a)=c$, $g(b)=d$, $g(a)=d$, $g(b)=c$.

$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{c\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{d\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{e}$$\textstyle{1}$

The coequalizer of $f,g$ is the trace monoid generated by $c,d,e$ with
equations $c=a=d=b$, $cd=dc$, $de=ed$. In the picture in the top line, it is
shown the independence relation for $M(\\{a,b\\})$, and in bottom for $M$.
Consequently, the coequalizer is equal to the free commutative monoid
generated by one element.

###  1.3 Independence preserving basic homomorphisms

We prove that the category of trace monoids and independence preserving
homomorphisms has all limits and colimits.

###### Definition 1.10

A basic homomorphism $f:M(E,I)\to M(E^{\prime},I^{\prime})$ is called
independence preserving if for all $a,b\in E$, the following implication is
carried out

$(a,b)\in I\Rightarrow(f(a)\not=f(b))~{}\vee~{}(f(a)=f(b)=1)~{}.$

It is easy to see, that this implication is equivalent to the condition

$(a,b)\in I\Rightarrow(f(a),f(b))\in
I^{\prime}~{}\vee~{}f(a)=1~{}\vee~{}f(b)=1~{}.$

It follows that the class of independence preserving homomorphisms is closed
under composition. Let $FPCM^{\|}\subset FPCM$ be the subcategory consisting
of all trace monoids and independence preserving basic homomorphisms.

Let us prove the existence of the products in the $FPCM^{||}$. For this
purpose we introduce the following partial independence relation.

###### Definition 1.11

Let $E$ be a set. A partial independence relation on $E$ is a subset
$R\subseteq E_{*}\times E_{*}$ satisfying the followng conditions:

  1. (i)

$(\forall a\in E_{*})~{}(a,*)\in R~{}\&~{}(*,a)\in R$;

  2. (ii)

$(\forall a\in E_{*})~{}(a,a)\in R\Rightarrow a=*$;

  3. (iii)

$(\forall a,b\in E_{*})~{}(a,b)\in R\Leftrightarrow(b,a)\in R$.

Let $IndRel$ be the category of pairs $(E_{*},R)$ consisting of pointed sets
$E_{*}$ and partial independence relations $R\subseteq E_{*}\times E_{*}$. Its
morphisms $(E_{*},R)\stackrel{{\scriptstyle
f}}{{\to}}(E_{*}^{\prime},R^{\prime})$ defined as pointed maps $f:E_{*}\to
E_{*}^{\prime}$ satisfying the following conditions:

$(a,b)\in R\Rightarrow(f(a),f(b))\in R^{\prime}.$

###### Proposition 1.12

The category $FPCM^{||}$ is isomorphic to $IndRel$.

Proof. Define the functor $FPCM^{||}\to IndRel$ as sending $M(E,I)$ to
$(E_{*},R)$ where $R=I\cup(E_{*}\times\\{*\\})\cup(\\{*\\}\times E_{*})$. The
inverse functor $IndRel\to IndRel$ carries any object $(E_{*},R)$ to the
monoid $M(E,I)$ where $I=R\setminus(E_{*}\times\\{*\\})\cup(\\{*\\}\times
E_{*})$. This functor send morphisms of $IndRel$ to independence preserving
morphisms. $\Box$

###### Corollary 1.13

The category $FPCM^{||}$ has all products.

Moreover, it is true the following

###### Theorem 1.14

The category $FPCM^{\|}$ has all limits. The inclusion functor
$FPCM^{\|}\subset FPCM$ preserves equalizers.

Proof. Since $FPCM^{\|}$ has products, it it enough to prove the existence
equalizers. For any pair of basic homorphisms
$\textstyle{M(E_{1},I_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{M(E_{2},I_{2})}$
in the category $FPCM$ its equalizer is the inclusion $M(E,I)\subseteq
M(E_{1},I_{1})$, where $E=\\{e\in E_{1}|f(e)=g(e)\\}$ and $I=I_{1}\cap(E\times
E)$. Inclusion preserves independence. Consider a trace monoid
$M(E^{\prime},I^{\prime})$ with a independence preserving homomorphism
$h:M(E^{\prime},I^{\prime})\to M(E_{1},I_{1})$ satisfying $fh=gh$. Since
$h(E^{\prime})\subseteq E$, there is a basic homomorphism $k$ drawn by dashed
arrow in the diagram:

|
---|---
$\textstyle{M(E,I)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\subseteq}$$\textstyle{M(E_{1},I_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{M(E_{2},I_{2})}$$\textstyle{M(E^{\prime},I^{\prime})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$

We have $k(e^{\prime})=h(e^{\prime})$ for all $e^{\prime}\in E^{\prime}$. The
homomorphism $h$ preserves independence. Hence, for all
$(a^{\prime},b^{\prime})\in I^{\prime}$, the condition $k(a^{\prime})=1\vee
k(b^{\prime})=1\vee(k(a^{\prime}),k(b^{\prime}))\in I_{1}$ holds. Thus, $k$
preserves independence. Equalizers is constructed in the category $FPCM$.
Therefore the inclusion $FPCM^{\|}\subset FPCM$ preserves equivalizers. $\Box$

We now turn to the colimit.

###### Theorem 1.15

The category $FPCM^{\|}$ is cocomplete.

Proof. The coproduct of trace monoids $\\{M(E_{i},I_{i})\\}_{i\in J}$ is a
monoid given by generators $\coprod\limits_{i\in J}E_{i}$ and relations
$ab=ba$ for all $(a,b)\in\coprod\limits_{i\in J}I_{i}$. It is easy to see that
it is coproduct in the category $FPCM^{||}$. Hence, it is sufficient to prove
the existence coequalizers. For this purpose, consider an arbitrary pair of
morphisms
$\textstyle{M(E_{1},I_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{M(E_{1},I_{1})}$
in the category $FPCM^{\|}$. Let $h:M(E_{2},I_{2})\to M(E,I)$ be the
coequalizer in the category $FPCM$. For each $h^{\prime}:M(E_{2},I_{2})\to
M(E^{\prime},I^{\prime})$, there exists a unique $k$ making commutative
triangle in the following diagram

---
$\textstyle{M(E_{1},I_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{M(E_{1},I_{1})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$$\scriptstyle{h}$$\textstyle{M(E,I)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\exists!k}$$\textstyle{M(E^{\prime},I^{\prime})}$

If $h^{\prime}$ preserves independence, then the following implication is
true:

$(\forall(a,b)\in I_{2})(h^{\prime}(a)=h^{\prime}(b)\Rightarrow
h^{\prime}(a)=1~{}\&~{}h^{\prime}(b)=1).$ (2)

Let $\equiv_{h}$ be the smallest congruence relation for which
$h(a)\equiv_{h}1$ and $h(b)\equiv_{h}1$ if $(a,b)\in I_{2}$ satisfies
$h(a)=h(b)$. Denote by $cls:M(E,I)\to M(E,I)/\equiv_{h}$ the homomorphism
assigning to any $e\in E_{*}$ its class $cls(e)$ of the congruence. If
$h^{\prime}$ preserves independence, then it follows from (2) and
$kh=h^{\prime}$ that

$(\forall(a,b)\in I_{2})k(h(a))=k(h(b))\Rightarrow
k(h(a))=1~{}\&~{}k(h(b))=1.$

We see that $k$ has constant values on each congruence class $cls(e)$ where
$e\in E_{*}$. Hence, we can define a map $k^{\prime}:M(E,I)/\equiv_{h}\to
M(E^{\prime},I^{\prime})$ by $k^{\prime}(cls(e))=k(e)$ for all $e\in E_{*}$.
The homomorphism $k^{\prime}$ is unique for which $k^{\prime}\circ cls\circ
h=h^{\prime}$. Therefore, $cls\circ h:M(E_{2},I_{2})\to M(E,I)/\equiv_{h}$ is
the coequalizer of $(f,g)$. $\Box$

In Example 1.9, we have $h(c)=h(d)=h(e)$. Since $(c,d)\in I_{2}$ and $(d,e)\in
I_{2}$, we have $cls\circ h(c)=1$, $cls\circ h(d)=1$, $cls\circ h(e)=1$.
Therefore, the coequalizer equals $\\{1\\}$.

##  2 Category of diagrams with various domains

This Section is auxiliary also does not contain new results. A diagram in a
category ${\mathcal{A}}$ is a functor ${\mathscr{C}}\to{\mathcal{A}}$ defined
on some small category ${\mathscr{C}}$. We shall consider categories of the
diagrams accepting values in some fixed category. Let us study the conditions
providing completeness or cocompleteness of this category.

###  2.1 Morphisms and objects in a digram category

Let ${\mathcal{A}}$ be a category and let $F:{\mathscr{C}}\to{\mathcal{A}}$ be
a diagram. Denote this diagram by $({\mathscr{C}},F)$ specifying its domain
${\mathscr{C}}$.

Let $({\mathscr{C}},F)$ and $({\mathscr{D}},G)$ be diagrams in
${\mathcal{A}}$. A morphism of the diagrams
$(\Phi,\xi):({\mathscr{C}},F)\to({\mathscr{D}},G)$ is given by a pair
$(\Phi,\xi)$ consisting of a functor $\Phi:{\mathscr{C}}\to{\mathscr{D}}$ and
natural transformation $\xi:F\to G\Phi$

|
---|---
$\textstyle{{\mathscr{C}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Phi}$$\scriptstyle{F}$$\scriptstyle{\xi\nearrow}$$\scriptstyle{G\Phi}$$\textstyle{{\mathscr{D}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{G}$$\textstyle{\mathcal{A}}$

Define the identity morphism by the formula
$1_{({\mathscr{C}},F)}=(1_{{\mathscr{C}}},1_{F})$ where
$1_{{\mathscr{C}}}:{\mathscr{C}}\to{\mathscr{C}}$ is the identity functor and
$1_{F}:F\to F$ is the identity natural transformation. The composition of
morphisms

$({\mathscr{C}},F)\stackrel{{\scriptstyle(\Phi,\xi)}}{{\to}}({\mathscr{D}},G)\stackrel{{\scriptstyle(\Psi,\eta)}}{{\to}}({\mathscr{E}},H)$

is defined as a pair $(\Psi\Phi,(\eta*\Phi)\cdot\xi)$ where
$\eta*\Phi:G\Phi\to H\Psi\Phi$ is a natural transformation given by a family
of morphisms specified as a family of morphisms

$(\eta*\Phi)_{c}=\eta_{\Phi(c)}:G(\Phi(c))\to
H(\Psi(\Phi(c))),~{}c\in\operatorname{{\rm Ob}}{\mathscr{C}},$

and $(\eta*\Phi)\cdot\xi$ is the composition of natural transformations
$F\stackrel{{\scriptstyle\xi}}{{\to}}G\Phi\stackrel{{\scriptstyle\eta*\Phi}}{{\to}}H\Psi\Phi$.
The composition is associative.

Let $Cat$ be the category of small categories and functors. Denote by
$(Cat,{\mathcal{A}})$ the category of diagrams in ${\mathcal{A}}$ and
morphisms of diagrams.

For any subcategory ${\mathfrak{C}}\subseteq Cat$, we consider diagrams
$F:{\mathscr{C}}\to{\mathcal{A}}$ defined on categories
${\mathscr{C}}\in{\mathfrak{C}}$. Such diagrams with morphisms
$(\Phi,\xi):({\mathscr{C}},F)\to({\mathscr{D}},G)$ where
$\Phi\in\operatorname{{\rm Mor}}{\mathfrak{C}}$, will be make a subcategory of
$(Cat,{\mathcal{A}})$. Denote this subcategory by
$({\mathfrak{C}},{\mathcal{A}})$.

###  2.2 Limits in a category of diagram

Let $J$ be a small category. In some cases, the diagrams are conveniently
denoted, specifying their values on objects. For example, we will denote by
$\\{A_{i}\\}_{i\in J}$ the diagram $J\to{\mathcal{A}}$ with values $A_{i}$ on
objects $i\in J$ and $A_{\alpha}:A_{i}\to A_{j}$ on morphisms $\alpha:i\to j$
of $J$. We say that a category ${\mathcal{A}}$ has $J$-limits if every diagram
$\\{A_{i}\\}_{i\in J}$ in ${\mathcal{A}}$ has a limit. If ${\mathcal{A}}$ has
$J$-limits for all small categories $J$, then ${\mathcal{A}}$ is said to be a
complete category or a category with all limits.

We will consider subcategories ${\mathfrak{C}}\subseteq Cat$ with $J$-limits.
But the $J$-limits in ${\mathfrak{C}}$ need not be isomorphic to the
$J$-limits in $Cat$.

###### Proposition 2.1

Let ${\mathcal{A}}$ be a complete category and let $J$ be a small category. If
a subcategory ${\mathfrak{C}}\subseteq Cat$ has $J$-limits, then the category
$({\mathfrak{C}},{\mathcal{A}})$ has $J$-limits. In particular, if
${\mathfrak{C}}\subseteq Cat$ is a complete category, then the category
$({\mathfrak{C}},{\mathcal{A}})$ is complete.

Proof. Let $\\{({\mathscr{C}}_{i},F_{i})\\}_{i\in J}$ be a diagram in
$({\mathfrak{C}},{\mathcal{A}})$. One given by a diagram
$\\{{\mathscr{C}}_{i}\\}_{i\in J}$ with functors
${\mathscr{C}}_{\alpha}:{\mathscr{C}}_{i}\to{\mathscr{C}}_{j}$ and natural
transformations $\varphi_{\alpha}:F_{i}\to F_{j}{\mathscr{C}}_{\alpha}$. Let
$p_{i}:\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\}\to{\mathscr{C}}_{i}$
is the limit cone of the diagram $\\{{\mathscr{C}}_{i}\\}_{i\in J}$ in
${\mathfrak{C}}$. The compositions $F_{i}\circ p_{i}$ belong to the category
${\mathcal{A}}^{\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\}}$. The
natural transformations
$F_{i}p_{i}\stackrel{{\scriptstyle\varphi_{\alpha}*p_{i}}}{{\to}}F_{j}{\mathscr{C}}_{\alpha}p_{i}\stackrel{{\scriptstyle=}}{{\to}}F_{j}p_{j}$
give the functor
$J\to{\mathcal{A}}^{\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\}}$. Let
$\underleftarrow{\lim}_{J}\\{F_{i}p_{i}\\}\in{\mathcal{A}}^{\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\}}$
be its limit. Denote by $\pi_{i}:\underleftarrow{\lim}_{J}\\{F_{i}p_{i}\\}\to
F_{i}p_{i}$ the limit cone. It easy to see that morphisms
$(p_{i},\pi_{i}):(\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\},\underleftarrow{\lim}_{J}\\{F_{i}p_{i}\\})\to({\mathscr{C}}_{i},F_{i})$
of diagrams make the cone over the diagram in
$({\mathfrak{C}},{\mathcal{A}})$. Considering an another cone
$(r_{i},\xi_{i}):({\mathscr{C}},F)\to({\mathscr{C}}_{i},F_{i})$ it can be seen
that there exists the unique morphism $(r,\xi)$ making the commutative
triangle

---
$\textstyle{({\mathscr{C}},F)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(r_{i},\xi_{i})}$$\scriptstyle{(r,\xi)}$$\textstyle{({\mathscr{C}}_{i},F_{i})}$$\textstyle{(\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\},\underleftarrow{\lim}_{J}\\{F_{i}p_{i}\\})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(p_{i},\pi_{i})}$

It follows that the limit is isomorphic to
$(\underleftarrow{\lim}_{J}\\{{\mathscr{C}}_{i}\\},\underleftarrow{\lim}_{J}\\{F_{i}p_{i}\\})$.
$\Box$

###  2.3 Colimits in a category of diagrams

Let ${\mathfrak{C}}\subseteq Cat$ be a subcategory. Consider an arbitrary
category ${\mathcal{A}}$. We shall prove that if the colimits exist in
${\mathfrak{C}}$, then those exist in $({\mathfrak{C}},{\mathcal{A}})$. For
any functor $\Phi:{\mathscr{C}}\to{\mathscr{D}}$, we denote by
$\operatorname{{\rm
Lan}}^{\Phi}:{\mathcal{A}}^{{\mathscr{C}}}\to{\mathcal{A}}^{{\mathscr{D}}}$
the left Kan extension functor [15]. Its properties are well described in
[15]. This functor is characterized as a left adjoint to the functor
$\Phi^{*}:\ mA^{{\mathscr{D}}}\to{\mathcal{A}}^{{\mathscr{C}}}$ assigning to
each diagram $F:{\mathscr{D}}\to{\mathcal{A}}$ the composition $F\circ\Phi$,
and to the natural transformation $\eta:F\to G$ the natural transformation
$\eta*\Phi$.

###### Proposition 2.2

Let ${\mathfrak{C}}\subseteq Cat$ be a category with all colimits. Then, for
any cocomplete category ${\mathcal{A}}$, the category
$({\mathfrak{C}},{\mathcal{A}})$ has all colimits.

Proof. Consider a diagram $\\{({\mathscr{C}}_{i},F_{i})\\}_{i\in J}$ in
$({\mathfrak{C}},{\mathcal{A}})$. As above, each morphism $\alpha:i\to j$ is
mapped to the natural transformation $\varphi_{\alpha}:F_{i}\to
F_{j}{\mathscr{C}}_{\alpha}$. Let
$\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}$ be the colimit of the
diagram in ${\mathfrak{C}}$. Denote by
$q_{i}:{\mathscr{C}}_{i}\to\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}$
morphisms of the colimit cone. Consider the Kan extensions $\operatorname{{\rm
Lan}}^{q_{i}}F_{i}$ and the units of adjunction

---
$\textstyle{{\mathscr{C}}_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{i}}$$\scriptstyle{F_{i}}$$\scriptstyle{\nearrow\eta_{i}}$$\textstyle{\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}}$$\textstyle{\mathcal{A}}$

We get the diagram in the category
${\mathcal{A}}^{\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}}$ consisting
of objects $\operatorname{{\rm Lan}}^{q_{i}}F_{i}$ and morphisms given at
$\alpha:i\to j$ by the compositions

$\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\stackrel{{\scriptstyle\operatorname{{\rm
Lan}}^{q_{i}}(\varphi_{\alpha})}}{{\to}}\operatorname{{\rm
Lan}}^{q_{i}}F_{j}{\mathscr{C}}_{\alpha}\stackrel{{\scriptstyle=}}{{\to}}\operatorname{{\rm
Lan}}^{q_{j}}\operatorname{{\rm
Lan}}^{{\mathscr{C}}_{\alpha}}F_{j}{\mathscr{C}}_{\alpha}\stackrel{{\scriptstyle\operatorname{{\rm
Lan}}^{q_{j}}(\varepsilon_{\alpha})}}{{\to}}\operatorname{{\rm
Lan}}^{q_{j}}F_{j}$

where $\varepsilon_{\alpha}:\operatorname{{\rm
Lan}}^{{\mathscr{C}}_{\alpha}}(F_{j}{\mathscr{C}}_{\alpha})\to F_{j}$ are
counits of adjunction. Let $\underrightarrow{\lim}^{J}\\{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\\}$ be the colimit of this diagram.

Prove that
$(\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\},\underrightarrow{\lim}^{J}\\{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\\})$ is a colimit of the diagram
$\\{({\mathscr{C}}_{i},F_{i})\\}_{i\in J}$ in
$({\mathfrak{C}},{\mathcal{A}})$. For this purpose, consider an arbitrary
(direct) cone $({\mathscr{C}}_{i},F_{i})\to({\mathscr{C}},F)$ over
$\\{({\mathscr{C}}_{i},F_{i})\\}_{i\in J}$ in the category
$({\mathfrak{C}},{\mathcal{A}})$. One is given by some functors

---
$\textstyle{{\mathscr{C}}_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r_{i}}$$\scriptstyle{F_{i}}$$\scriptstyle{\nearrow\psi_{i}}$$\textstyle{{\mathscr{C}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{F}$$\textstyle{\mathcal{A}}$

and natural transformations $\psi_{i}:F_{i}\to Fr_{i}$ for which the following
diagrams are commutative

---
$\textstyle{({\mathscr{C}}_{i},F_{i})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{({\mathscr{C}}_{\alpha},\varphi_{\alpha})}$$\scriptstyle{(r_{i},\psi_{i})}$$\textstyle{({\mathscr{C}},F)}$$\textstyle{({\mathscr{C}}_{j},F_{j})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(r_{j},\psi_{j})}$
$\textstyle{F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{i}}$$\scriptstyle{\varphi_{\alpha}}$$\textstyle{Fr_{i}}$$\textstyle{F_{j}{\mathscr{C}}_{\alpha}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{j}*{\mathscr{C}}_{\alpha}}$$\textstyle{Fr_{j}{\mathscr{C}}_{\alpha}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Since $\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}$ is the colimit in
${\mathfrak{C}}$, the unique functor
$r:\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}\to{\mathscr{C}}$ is
corresponded to the functors of this cone
$r_{i}:{\mathscr{C}}_{i}\to{\mathscr{C}}$, such that $r_{i}=rq_{i}$ dor all
$i\in J$ where
$q_{i}:{\mathscr{C}}_{i}\to\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}$
is the colimit cone.

For any $i\in J$, the functor $\operatorname{{\rm Lan}}^{q_{i}}$ is left
adjoint to $q_{i}^{*}$. Hence, there exists a bijection between natural
transformations

$F_{i}\stackrel{{\scriptstyle\psi_{i}}}{{\to}}Fr_{i}=Frq_{i}\quad\mbox{ and
}\quad\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\stackrel{{\scriptstyle\overline{\psi_{i}}}}{{\to}}Fr\,.$

This bijection maps each commutative triangle in
${\mathcal{A}}^{{\mathscr{C}}_{i}}$ to the commutative triangle in
${\mathcal{A}}^{\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}_{i\in J}}$:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
13.62534pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
22.05951pt\raise 6.1111pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\psi_{i}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 43.37631pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
0.0pt\raise-19.63664pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.8264pt\hbox{$\scriptstyle{\varphi_{\alpha}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.43999pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
43.37631pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{Frq_{i}}$}}}}}}}{\hbox{\kern-13.62534pt\raise-39.2733pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{F_{j}{\mathscr{C}}_{\alpha}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
16.25325pt\raise-45.75226pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.38214pt\hbox{$\scriptstyle{\psi_{j}*{\mathscr{C}}_{\alpha}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
37.62534pt\raise-39.2733pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
37.62534pt\raise-39.2733pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{Frq_{j}{\mathscr{C}}_{\alpha}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\hbox{\kern-1.0pt\raise
0.0pt\hbox{\lx@xy@droprule}}\hbox{\kern 1.0pt\raise
0.0pt\hbox{\lx<EMAIL_ADDRESS>0.0pt\hbox{\lx@xy@droprule}}\hbox{\kern 1.0pt\raise
0.0pt\hbox{\lx<EMAIL_ADDRESS>0.0pt\hbox{\lx@xy@droprule}}\hbox{\kern 1.0pt\raise
0.0pt\hbox{\lx@xy@droprule}}}}\ignorespaces}}}}\ignorespaces\quad\mapsto\quad\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
18.72676pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
0.0pt\raise-29.3911pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
20.51558pt\raise 5.83888pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.83888pt\hbox{$\scriptstyle{\overline{\psi_{i}}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 42.72676pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
42.72676pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{Fr}$}}}}}}}{\hbox{\kern-18.72676pt\raise-40.42996pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\operatorname{{\rm
Lan}}^{q_{j}}F_{j}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
24.79097pt\raise-26.05386pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.83888pt\hbox{$\scriptstyle{\overline{\psi_{j}}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 48.16985pt\raise-3.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces}}}}\ignorespaces$

For the diagram

|
---|---
$\textstyle{F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{i}}$$\scriptstyle{\varphi_{\alpha}}$$\textstyle{Frq_{i}=Frq_{j}{\mathscr{C}}_{\alpha}}$$\textstyle{F_{j}{\mathscr{C}}_{\alpha}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{j}*{\mathscr{C}}_{\alpha}}$

we have the commutative diagram in ${\mathcal{A}}^{{\mathscr{C}}_{j}}$

|
---|---
$\textstyle{\operatorname{{\rm
Lan}}^{{\mathscr{C}}_{\alpha}}F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\varphi_{\alpha}}}$$\scriptstyle{\overline{\psi_{i}}}$$\textstyle{Frq_{j}}$$\textstyle{F_{j}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{j}}$

Applying $\operatorname{{\rm Lan}}^{q_{j}}$, we obtain the commutative diagram

|  |
---|---|---
$\textstyle{\operatorname{{\rm Lan}}^{q_{j}}\operatorname{{\rm
Lan}}^{{\mathscr{C}}_{\alpha}}F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{{\rm
Lan}}^{q_{j}}{\overline{\varphi_{\alpha}}}}$$\scriptstyle{\operatorname{{\rm
Lan}}^{q_{j}}{\overline{\psi_{i}}}}$$\textstyle{\operatorname{{\rm
Lan}}^{q_{j}}Frq_{j}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\varepsilon_{j}}_{Fr}}$$\textstyle{Fr}$$\textstyle{\operatorname{{\rm
Lan}}^{q_{j}}F_{j}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{{\rm
Lan}}^{q_{j}}({\psi_{j}})}$

which leads us to the (direct) cone over the diagram $\\{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\\}_{i\in J}$

---
$\textstyle{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{Fr}$$\textstyle{\operatorname{{\rm
Lan}}^{q_{j}}F_{j}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

This cone gives the morphism $\underrightarrow{\lim}^{J}\\{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\\}\to Fr$ in
${\mathcal{A}}^{\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\}}$ which
define a unique morphism in $({\mathfrak{C}},{\mathcal{A}})$ making
commutative triangles

---
$\textstyle{(\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\},\underrightarrow{\lim}^{J}\\{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\\})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{({\mathscr{C}},F)}$$\textstyle{({\mathscr{C}}_{i},F_{i})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Therefore, the diagram
$(\underrightarrow{\lim}^{J}\\{{\mathscr{C}}_{i}\\},\underrightarrow{\lim}^{J}\\{\operatorname{{\rm
Lan}}^{q_{i}}F_{i}\\})$ in ${\mathcal{A}}$ is the colimit of the diagram
$\\{({\mathscr{C}}_{i},F_{i})\\}_{i\in J}$ in the category
$({\mathfrak{C}},{\mathcal{A}})$. $\Box$

##  3 Category of pointed polygons on trace monoids

We apply auxiliary propositions from section 2 to categories
${\mathcal{A}}={\rm Set}_{*}$, ${\mathfrak{C}}=FPCM$ and
${\mathfrak{C}}=FPCM^{\|}$. Then we shall establish communications between a
category of asynchronous systems and categories of right $M(E,I)$-sets and we
investigate a category of asynchronous systems and polygonal morphisms.

###  3.1 Category of state spaces

A state space $(M(E,I),X)$ consists of a trace monoid $M(E,I)$ with an action
on a pointed set $X$ by some operation $\cdot:X\times M(E,I)\to X$, $x\mapsto
x\cdot w$ for $x\in X$, $w\in M(E,I)$. Since the monoid is a category with a
unique object, we can consider the state space as a functor $X:M(E,I)^{op}\to
Set_{*}$ sending the unique object to the pointed set $X$ and morphisms $w\in
M(E,I)$ to maps $X(w):X\to X$ given as $X(w)(x)=x\cdot w$. Here we denote by
$X$ the pointed set on which the monoid acts as well as functor defined by
this action.

###### Definition 3.1

A morphism of state spaces

$(M(E,I),X)\to(M(E^{\prime},I^{\prime}),X^{\prime})$

is a pair $(\eta,\sigma)$ where $\eta:M(E,I)\to M(E^{\prime},I^{\prime})$ is a
basic homomorphism and $\sigma:X\to X^{\prime}\circ\eta^{op}$ is a natural
transformation.

A morphism of state spaces is possible to represent by means of the diagram

|
---|---
$\textstyle{M(E,I)^{op}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{X}$$\scriptstyle{\sigma\nearrow}$$\scriptstyle{\eta^{op}}$$\textstyle{M(E^{\prime},I^{\prime})^{op}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{X^{\prime}}$$\textstyle{Set_{*}}$

The category of state space is isomorphic to $(FPCM,Set_{*})$.

By Proposition 2.1, if a subcategory ${\mathfrak{C}}\subseteq Cat$ has
$J$-limits, then $({\mathfrak{C}},{\rm Set}_{*})$ has $J$-limits. For
${\mathfrak{C}}=FPCM$ and for discrete category $J$ with $\operatorname{{\rm
Ob}}(J)=\\{1,2\\}$, it follows from Proposition 2.1, the following

###### Proposition 3.2

Let $(M(E_{1},I_{1}),X_{1})$ and $(M(E_{2},I_{2}),X_{2})$ be state spaces.
Their product in $(FPCM,Set_{*})$ is a state space

$(M(E_{1},I_{1})\prod M(E_{2},I_{2}),X_{1}\circ\pi_{1}^{op}\times
X_{2}\circ\pi_{2}^{op})$

where $\pi_{i}:M(E_{1},I_{1})\prod M(E_{2},I_{2})\to M(E_{i},I_{i})$ are the
projections of the product in the category $FPCM$ for $i\in\\{1,2\\}$.

###### Definition 3.3

A morphism $(\eta,\sigma):(M(E,I),X)\to(M(E^{\prime},I^{\prime}),X^{\prime})$
of state spaces is independence preserving if $\eta:M(E,I)\to
M(E^{\prime},I^{\prime})$ is independence preserving.

Let $(FPCM^{\|},Set_{*})\subset(FPCM,Set_{*})$ be the subcategory of all state
spaces and independence preserving morphisms.

###### Proposition 3.4

The categories $(FPCM,Set_{*})$ and $(FPCM^{\|},Set_{*})$ are complete.

Proof. The category $FPCM$ is complete by Theorem 1.6 and $FPCM^{\|}$ is
complete by Theorem 1.14. Proposition 2.1 gives completeness of
$(FPCM,Set_{*})$ and $(FPCM^{\|},Set_{*})$.

###### Proposition 3.5

The categories $(FPCM,Set_{*})$ and $(FPCM^{\|},Set_{*})$ are cocomplete.

Proof. First statement follows from Theorem 1.8 and Proposition 2.2 applied to
${\mathfrak{C}}=FPCM$ and ${\mathcal{A}}=Set_{*}$. The second statement
follows from Theorem 1.15 and Proposition 2.2. $\Box$.

###  3.2 Category of weak asynchronous system and polygonal morphisms

###### Definition 3.6

The weak asynchronous system ${\mathcal{A}}=(S,s_{0},E,I,\operatorname{{\rm
Tran}})$ consist of a set $S$ which elements called states, an initial state
$s_{0}\in S_{*}$, a set $E$ of events, the irreflective symmetric relation
$I\subseteq E\times E$ of independence, satisfying the conditions

  * •

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

  * •

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

If we add to Definition 3.6 the conditions $s_{0}\in S$ and $S\not=\emptyset$,
then we obtain asynchronous systems in the sense of M. Bednarczyk [1]. If more
than that, we require the condition $(\forall e\in E)(\exists e,e^{\prime}\in
S)~{}(s,e,s^{\prime})\in\operatorname{{\rm Tran}}$, then we get an
asynchronous transition system [19].

###### Lemma 3.7

Every weak asynchronous system $(S,s_{0},E,I,\operatorname{{\rm Tran}})$ gives
a state space $(M(E,I),S_{*})$ with a distinguished element $s_{0}\in S_{*}$
wherein the action is defined by

$(s,[e_{1}\cdots e_{n}])\mapsto(\ldots((s\cdot e_{1})\cdot e_{2})\ldots\cdot
e_{n}),$

for all $s\in S_{*}$ and $e_{1}$, …, $e_{n}\in E$. Here for $s\in S$, $e\in
E$, we let

$s\cdot e=\left\\{\begin{array}[]{cl}s^{\prime},&\mbox{ if
}(s,e,s^{\prime})\in\operatorname{{\rm Tran}};\\\ ,&\mbox{ if there is no
}s^{\prime}\mbox{ such that }(s,e,s^{\prime})\in\operatorname{{\rm
Tran}}.\end{array}\right.$

This correspondence is one-to-one. The inverse map takes any state space
$(M(E,I),S_{*})$ and $s_{0}\in S_{*}$ to an asyncronous system
$(S,s_{0},E,I,\operatorname{{\rm Tran}})$ where $\operatorname{{\rm
Tran}}=\\{(s,e,s\cdot e)~{}|~{}s\in S~{}\&~{}s\cdot e\in S\\}$.

In other words, the weak asynchronous system and hence the asynchronous
transition system can be viewed as the state space $(M(E,I),S_{*})$ with
distinguished $s_{0}\in S_{*}$.

###### Definition 3.8

A morphism of weak asynchronous systems
$(f,\sigma):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ consists of partial maps
$f:E{\rightharpoonup}E^{\prime}$ and $\sigma:S{\rightharpoonup}S^{\prime}$
satifying the following conditions

  1. (i)

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

  2. (ii)

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

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

  3. (iii)

for each pair $(e_{1},e_{2})\in I$ such that $f(e_{1})$ and $f(e_{2})$ are
defined, the pair $(f(e_{1}),f(e_{2}))$ must belong to $I^{\prime}$.

If $s_{0}\not=*$, $s^{\prime}_{0}\not=*$ and $\sigma:S\to S^{\prime}$ is
defined on the whole $S$, then these conditions gives a morphism of
asynchronous systems in the sense of [1]. Following [1] denote by
${\mathcal{A}S}$ the category of asynchronous systems.

###### Definition 3.9

A morphism of weak asynchronous systems
$(f,\sigma):{\mathcal{A}}\to{\mathcal{A}}^{\prime}$ is polygonal if
$(f,\sigma)$ defines the independence preserving morphism of the corresponding
state spaces.

Denote by ${\mathcal{A}S^{\flat}}$ the category of asynchronous systems and
polygonal morphisms. We show that the category ${\mathcal{A}S}$ is not a
subcategory of ${\mathcal{A}S^{\flat}}$.

###### Proposition 3.10

A morphism $(\eta,\sigma):(S,s_{0},E,I,\operatorname{{\rm
Tran}})\to(S^{\prime},s^{\prime}_{0},E^{\prime},I^{\prime},\operatorname{{\rm
Tran}}^{\prime})$ in the category ${\mathcal{A}S}$ is polygonal if and only if
for any $s_{1}\in S$, $e\in E$, $s^{\prime}_{2}\in S^{\prime}$ the following
implication holds

$(\sigma(s_{1}),\eta(e),s^{\prime}_{2})\in\operatorname{{\rm
Tran}}^{\prime}~{}\Rightarrow~{}(\exists s_{2}\in
S)(s_{1},e,s_{2})\in\operatorname{{\rm Tran}}.$

Proof. If $(\eta,\sigma)$ is a polygonal morphism, then for any $s_{1}\in S$
and $e\in E$ such those $s_{1}\cdot e=*$, we have
$\sigma(s_{1})\cdot\eta(e)=\sigma(s_{1}\cdot e)=*$. It follows that a morphism
of asynchronous systems is polygonal if and only if for all $s_{1}\in S$ and
$e\in E$ the following implication holds $s_{1}\cdot
e=*\Rightarrow\sigma(s_{1})\cdot\eta(e)=*$. By the law of contraposition, we
obtain for all $s_{1}\in S$ and $e\in E$ that

$(\exists s^{\prime}_{2}\in
S^{\prime})(\sigma(s_{1}),\eta(e),s^{\prime}_{2})\in\operatorname{{\rm
Tran}}^{\prime}\Rightarrow(\exists s_{2}\in
S)(s_{1},e,s_{2})\in\operatorname{{\rm Tran}}.$ (3)

Taking out from the formula (3) the variable $s^{\prime}_{2}$ with the
quantifier, we get

$(\forall s^{\prime}_{2}\in
S^{\prime})\left((\sigma(s_{1}),\eta(e),s^{\prime}_{2})\in\operatorname{{\rm
Tran}}^{\prime}\Rightarrow(\exists s_{2}\in
S)(s_{1},e,s_{2})\in\operatorname{{\rm Tran}}\right).$

Adding to the formula the quantifiers $(\forall s_{1}\in S)(\forall e\in E)$,
we obtain the required assertion. $\Box$

Let ${\rm pt}_{*}=\\{p,*\\}$ be a state space with the monoid
$M(\emptyset,\emptyset)=\\{1\\}$. Associating with weak asynchronous system
the morphism of state spaces ${\rm pt}_{*}\to(M(E,I),S_{*})$ defined as
$p\mapsto s_{0}$, we obtain

###### Proposition 3.11

${\mathcal{A}S^{\flat}}$ is isomorphic to the comma category ${\rm
pt}_{*}/(FPCM^{\|},{\rm Set}_{*})$.

For any complete category ${\mathcal{A}}$ and object $A\in\operatorname{{\rm
Ob}}{\mathcal{A}}$, the comma-category $A/{\mathcal{A}}$ is complete. It
follows from 3.4 and 3.11 the following

###### Theorem 3.12

The category ${\mathcal{A}S^{\flat}}$ is complete.

The completeness of ${\mathcal{A}S}$ is shown in [1]. It follows from
Propositions 3.5 and 3.11 the following

###### Theorem 3.13

The category ${\mathcal{A}S^{\flat}}$ is cocomplete.

##  4 Conclusion

There are possible applications of the results related with building adjoint
functors between the category of ${\mathcal{A}S^{\flat}}$ and the category of
higher dimensional automata. Unlabeled semiregular higher dimensional
automation [10] is a contravariant functor from the category of cubes into the
category ${\rm Set}$. Let $\Upsilon_{sr}$ be a category of unlabeled
semiregular higher dimensional automata and natural transformations. By [8,
Proposition II.1.3] for each functor from the category of cubes to the
category $(FPCM^{||},{\rm Set})$, there exists a pair of adjoint functors
between the categories $\Upsilon_{sr}$ and $(FPCM^{||},{\rm Set})$. We can
take the functor assigning to $n$-dimensional cube the state space
$({\,\mathbb{N}}^{n},h_{{\,\mathbb{N}}^{n}})$ where
$h_{{\,\mathbb{N}}^{op}}:{\,\mathbb{N}}^{op}\to{\rm Set}$ is the contravariant
functor of morphisms. So, we get left adjoint to the composition
$(FPCM^{||},{\rm Set}_{*})\to(FPCM^{||},{\rm Set})\to\Upsilon_{sr}$. Taking
initial point, we obtain adjoint functors between ${\mathcal{A}S^{\flat}}$ and
the category of higher dimensional automata with the initial point.

Considering the comma categories, we can compare the labelled asynchronous
systems with labelled higher dimensional automata.

Event structures and Petri nets can be considered as asynchronous systems.
Therefore, applications of polygonal morphisms for the study of Petri nets and
event structures are possible.

## References

  * [1] M. Bednarczyk,  Categories of Asynchronous Systems, University of Sussex, Brighton, 1987. – 230p.
  * [2] M. A. Bednarczyk, L. Bernardinello, B. Caillaud, W. Pawlowski, L. Pomello,  “Modular System Development with Pullbacks”,  Applications and Theory of Petri Nets 2003,  Lecture Notes in Computer Science, 2679, Springer-Verlag, Berlin, 2003, 140–160
  * [3] M. A. Bednarczyk, A. M. Borzyszkowski, R. Somla,  “Finite Completeness of Categories of Petri Nets”,  Fundamenta Informaticae, 43 (2000) 21 -48.
  * [4] P. Cartier, D. Foata,  Problèmes combinatories de commutation et réarrangements,  Lecture Notes in Math., 85, Springer-Verlag, Berlin, 1969.
  * [5] V. Diekert,  Combinatorics on Traces,  Lecture Notes in Computer Science, 454, Springer-Verlag, Berlin, 1990.
  * [6] V. Diekert, Y. Métivier,  Partial Commutation and Traces,  Handbook of formal languages, 3, Springer-Verlag, New York, 1997, 457–533.
  * [7] L. Fajstrup, E. Goubault, M. Raußen,  “Detecting Deadlocks in Concurrent Systems”,  Concur’98,  Lecture Notes in Computer Science, 1466, Springer-Verlag, Berlin, 1998, 332–346
  * [8] P. Gabriel, M. Zisman, Calculus of Fractions and Homotopy Theory. Springer, Berlin (1967)
  * [9] E. Goubault,  “Labeled cubical sets and asynchronous transitions systems: an adjunction”,  In Preliminary Proceedings CMCIM’02, 2002.
http://www.lix.polytechnique.fr/$\tilde{~{}}$goubault/papers/cmcim02.ps.gz

  * [10] E. Goubault,  The Geometry of Concurrency,  Ph.D. Thesis, Ecole Normale Supérieure, 1995, 349 p.; http://www.dmi.ens.fr/$\widetilde{~}{}$goubault
  * [11] E. Goubault and S. Mimram. “Formal relationships between geometrical and classical models for concurrency.” Electronic Notes in Theoretical Computer Science 283 (2012): 77-109.
  * [12] A. A. Husainov,  “On the homology of small categories and asynchronous transition systems”,  Homology Homotopy Appl., 6:1 (2004), 439–471. http://www.rmi.acnet.ge/hha
  * [13] 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

  * [14] A. A. Khusainov, “Homology groups of asynchronous systems, Petri nets, and trace languages.” Sibirskie Élektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] 9 (2012): 13-44.
  * [15] S. Mac Lane, Categories for the Working Mathematician. Graduate texts in mathematics, vol. 5. Springer, New York (1998)
  * [16] A. Mazurkiewicz,  “Basic notions of trace theory”,  Linear time, branching time and partial order in logics and models for concurrency, Lecture Notes in Computer Science, 354, Springer-Verlag, Berlin, 1989, 285–363
  * [17] R. Milner, Communication and concurrency, International Series in Computer Science. Prentice Hall, New York, 1989.
  * [18] M. Nielsen,  “Models for concurrency”,  Mathematical Foundations in Computer Science 1991,  Lecture Notes in Computer Science, 520, Springer-Verlag, Berlin, 1991, 43–46
  * [19] G. Winskel and M. Nielsen,  Models for Concurrency, Handbook of Logic in Computer Science, Vol. IV, ed. Abramsky, Gabbay and Maibaum. Oxford University Press, 1995\. P.1–148.