# Cubical Sets and Trace Monoid Actions

Authors: Ahmet A. Husainov
Journal: The Scientific World Journal
 (2013)

---

## Abstract

This paper is devoted to connections between trace monoids and cubical sets. We prove that the category of trace monoids is isomorphic to the category of generalized tori and it is a reflective subcategory of the category of cubical sets. Adjoint functors between the categories of cubical sets and trace monoid actions are constructed. These functors carry independence preserving morphisms in the independence preserving morphisms. This allows us to build adjoint functors between the category of weak asynchronous systems and the category of higher dimensional automata.


---

## Body

## 1. Introduction

In this paper, it is established that the category of generalized tori is isomorpic to the category of trace monoids and basic homomorphisms. It is shown that the category of generalized tori is reflective subcategory of the category of cubical sets. Adjoint functors between the category of cubical sets and the category of trace monoids acting on sets are constructed. These functors carry independence preserving morphisms in the independence preserving morphisms. The results are used to compare asynchronous systems and higher dimensional automata for modelling of concurrent systems.The problem of comparing the mathematical models of concurrent systems using adjoint functors has always been of great interest [1–5]. In [2], Goubault introduced automata with concurrency relations for generalization of asynchronous systems. The category ACR of automata with concurrency relations is isomorphic to the category of 2-skeletion of a category HTS of higher dimensional transition systems. The truncation gives the desired left adjoint to the inclusion functor ACR→HTS. Moreover, in the thesis [3], Goubault proved that there are adjoint functors between the category of semiregular higher dimensional automata and the category ATS of asynchronous transition systems satisfying the axiom of confluence.But the asynchronous system(1)
consisting of three states and two transitions with the independence relation I={(a,b),(b,a)} does not satisfy the confluence condition and is not an automation with concurrency relation. Therefore, it remains an open problem of existence of a left adjoint functor from the category of higher dimensional automata in the category containing asynchronous systems which are not confluent.This problem is solved in this paper.We propose a category that includes all asynchronous systems and admits adjoint functors with the category of higher dimensional automata. By [6, 7], this category may be useful for studying the homology groups of asynchronous systems.This work consists of two sections. In the first, we construct the adjoint functors between the categories of trace monoids and cubical sets. In the second, section we start with the construction of adjoint functors between the category of trace monoids acting on sets and the category of cubical sets. Then, we build adjoint functors between the categories of asynchronous systems and higher dimensional automata.


## 2. Trace Monoids and Cubical Sets

Introduce a categoryFPCM of trace monoids and basic homomorphisms. Consider a category of cubical sets. Introduce generalized tori. Construct the adjoint functors between the category FPCM of trace monoids and cubical sets.


### 2.1. Preliminaries

Throughout the paper,Set denotes the category of sets and maps.For any category𝒜 and objects A,A′∈𝒜, let 𝒜(A,A′) denotes the set of morphisms f:A→A′. Let 𝒜op be the opposite category. Adiagram (of objects) in 𝒜 is any functor from some small category J to 𝒜. Let {D(j)}j∈J denotes a diagram D:J→𝒜. 𝒜J will always denote the category of diagrams J→𝒜 and natural trasformations between them.LetS:𝒞→𝒟 be a functor between small categories and let 𝒜 be an arbitrary category. Consider the functor (-)∘S:𝒜𝒟→𝒜𝒞 defined on objects as F↦F∘S and on morphisms as η↦η★S. Left derived functor LanS:𝒜𝒞→𝒜𝒟 to (-)∘S is called a left Kan extension alongS.LetY′:𝒟→Set𝒟op be the Yoneda functor described in [8, III.2, page 62]. For each functor H:𝒟→𝒜, we consider the functor D:𝒜→Set𝒟op defined on objects A∈𝒜 by its values D(A)(-)=𝒜(H(-),A) with the obvious extension to morphisms.Proposition 1 (see [9, Proposition II.1.3]).
Let𝒜 be a cocomplete category and let 𝒟 be a small category. For every functor H:𝒟→𝒜 the functor D:𝒜→Set𝒟op has a left adjoint functor isomorphic to the left Kan extension G=LanY′H:
(2)For anyX∈Set𝒟op, we have LanY′X=lim⟶𝒟↓X(H∘PX) where 𝒟↓X=Y′↓X denotes the comma category of objects Y′-over X for the Yoneda functor Y′:𝒟→Set□op and P=PX:𝒟↓X→𝒟 is the projection [8].We can obtain by the theory of ends [8, Theorem X.4.1, page 240] the following.Proposition 2 (see [8]).
For eachX∈Set𝒟op, G(X) equals the colimit of a diagram defined on a directed bipartite graph consisting of morphisms
(3)
where f:a→b runs all morphisms of the category 𝒟.


### 2.2. Trace Monoids

LetE be a set. A binary relation I⊆E×E is irreflexive if (∀a∈E)(a,a)∉I. One is symmetric if (∀(a,b)∈E×E)(a,b)∈I⇒(b,a)∈I. An independence relation on E is an arbitrary irreflexive symmetric binary relation I⊆E×E. In this case, elements a,b∈E are independent if (a,b)∈I.LetE* be the set of all words  a1a2⋯an composed of lettersa1,a2,…,an∈E for all n⩾0. Then, E* is the monoid with the operation of concatenation by the following formula:
(4)(a1⋯an)(b1⋯bm)=a1⋯anb1⋯bm.Identity element1 is the empty word.LetI be an independence relation on E. Define an equivalence relation ≡I on E* assuming w1≡w2 if the word w2 can be obtained from w1 by a finite sequence permutations of adjacent independent elements. For any w∈E*, its equivalence class [w] is called a trace. It is easy to see that the operation [w1][w2]=[w1w2] transforms the set of equivalence classes E*/≡ in a monoid. This monoid is called a trace monoidM(E,I).Our definition of trace monoid is different from that given in [10]. We suppose that E can be infinite.In some cases, we omit square brackets and writew∈M(E,I) instead of [w]∈M(E,I). If I=∅, then M(E,I) is the free monoidE*. If I=((E×E)∖{(a,a)∣a∈E}), then M(E,I) is the free commutative monoid ℕ(E).Definition 3.
A homomorphismf:M(E,I)→M(E′,I′) is basic if f(E)⊆E′∪{1}.Ifw=e1⋯en∈M(E,I) for some e1∈E,…,en∈E, then n is the length of trace w.Proposition 4.
Every diagramD:J→FPCM has the colimit in FPCM.Proof.
LetD(j)=M(Ej,Ij) for j∈J and let ∐j∈J‍D(j) be the coproduct in the category of monoids Mon. Then, the colimit lim⟶J{D(j)}j∈J is equal to the quotient monoid ∐j∈J‍M(Ej,Ij)/≡I where ≡I is the smallest congruence relation satisfying e≡ID(i→αj)(e) for all i∈J, j∈J, α∈J(i,j), e∈Ei. A more detailed proof can be found in the preprint [11].Definition 5.
A basic homomorphismf:M(E,I)→M(E′,I′) is independence preserving if for all a,b∈E the following implication holds:
(5)(a,b)∈I⟹(f(a)≠f(b))∨(f(a)=f(b)=1).This is equivalent to the following condition:(6)(a,b)∈I⟹(f(a),f(b))∈I′∨f(a)=1∨f(b)=1.It follows that the composition of independence preserving homomorphisms is independence preserving. LetFPCM∥⊂FPCM be a subcategory consisting of all trace monoids and basic independence preserving homomorphisms.


### 2.3. Cubical Sets and Trace Monoids

Acubical set(Xn,∂in,ν,ϵin) is a sequence of sets Xn, n∈ℕ with two family of maps(i)
∂in,ν:Xn→Xn-1, 1⩽i⩽n, ν∈{0,1}, (face operators)(ii)
ϵin:Xn→Xn+1, 1⩽i⩽n+1, (degeneracies)satisfying the following equations:(7)∂in-1,α∂jn,β=∂j-1n-1,β∂in,α,2⩽i<j⩽n,ϵin+1ϵjn=ϵj+1n+1ϵin,1⩽i⩽j⩽n+1,∂in+1,αϵjn={ϵj-1n-1∂in,α,1⩽i<j⩽n+1,ϵjn-1∂i-1n,α,1⩽j<i⩽n+1,1Xn,i=j.Amorphismf:X→Yof cubical sets is a family of maps fn:Xn→Yn commuting with the face operators and degeneracies. Let Cube be a category of cubical sets and morphisms.Let□ be the category consisting of the partially ordered sets 𝕀n={0,1}n and maps admitting decompositions by the following maps:
(8)δin,ν(x1,…,xn)=(x1,…,xi-1,ν,xi,…,xn),εin(x1,…,xn)=(x1,…,xi-1,xi+1,…xn).By settingX(𝕀n)=Xn, X(δin,ε)=∂in,ε, X(εin)=ϵin, we can consider every cubical set as functor □op→Set. A morphism of cubical sets can be considered as natural transformations. We will identify the category Cube with Set□op.Introduce generalized tori.Definition 6.
LetM(E,I) be a trace monoid. Generalized torusTM(E,I) is a cubical set consisting of sets T0M(E,I)={1} and
(9)TnM(E,I)={eiej=ejei∀1⩽i<j⩽n}(e1,…,en)∣ei∈E∪{1}∀1⩽i⩽n,eiej=ejei∀1⩽i<j⩽n}
for all n⩾1. The maps ∂in,ν, ϵin are defined by
(10)∂in,ν(e1,…,en)=(e1,…,ei-1,ei+1,…,en),ϵin(e1,…,en)=(e1,…,ei-1,1,ei,…,en).The mapM(E,I)↦TM(E,I) extends to a functor T:FPCM→Set□op which assigns to each basic homomorphism f:M(E,I)→M(E′,I′) a morphism of cubical sets given by a family of maps Tnf:TnM(E,I)→TnM(E′,I′) defined as
(11)Tnf(e1,…,en)=(f(e1),…,f(en)).
And conversely, since every morphism of cubical sets commutes with face operators, any morphism ηn:TnM(E,I)→TnM(E′,I′) can be given by the maps (e1,…,en)↦(η1(e1),…,η1(en)) defined by some η1:E→E′∪{1}. So, it holds the following.Proposition 7.
The functorT:FPCM→Set□op is full and faithful.We will prove the following.Theorem 8.
The functorT:FPCM→Set□op has a left adjoint G:Set□op→FPCM. For every cubical set X, the trace monoid G(X) can be given by the generator set X1/≡ by a smallest equivalence relation on X1 identifying ∂i2,0x2≡∂i2,1x2 for all x2∈X2 and i∈{1,2}, with the following relations for the equivalence classes:
(12)[∂12,0x2][∂22,0x2]=[∂22,0x2][∂12,0x2],∀x2∈X2,[ϵ10(x0)]=1,∀x0∈X0.Proof.
For the construction of left adjoint toT, we use Propositions 1 and 2. With this aim, define a functor H:□→FPCM by setting H(𝕀n)=ℕn on objects of □. Let H(δin,ν)(ak1,…,akn)=(ak1,…,aki-1,1,aki,…,akn) for all 1⩽i⩽n and ε∈{0,1}. Set H(εin):ℕn→ℕn-1 by
(13)H(εin)(ak1,…,akn)=(ak1,…,aki-1,aki+1,…,akn).
Here, ak∈ℕ are elements of the free monoid generated by one element ℕ={1,a,a2,…}. Let ai∈ℕn be the tuple (1,…,1,a,1,…,1) in which the generator a is located on the ith place. In particular, a1=(a,1,…,1).
Basic homomorphismsℕn→M(E,I) are given by values at ai, 1⩽i⩽n. Therefore, FPCM(ℕn,M(E,I))≅TnM(E,I). It follows that the functor T is isomorphic to D acting by D(M)=FPCM(H(-),M):□op→Set. Hence, the functor T has a left adjoint G.
By Proposition2, the object G(X) is isomorphic to quotient monoid of ∐n⩾0,x∈Xn‍(H(𝕀n))x by the smallest congruence relation identificating the pairs:
(14)(x,H(f)(u))≡(X(f)(x),u),∀f∈(𝕀m,𝕀n),u∈H(𝕀m),x∈Xn.
Element u∈ℕm equals (ak1,…,akm) for some nonnegative integers ki.
Substitutingf by δin-1,ν and εin+1 and using the commutativity of monoids {x}×ℕn, we conclude that monoid G(X) can be given by the generators (x,aj) with the relations
(15)(x,ai)(x,aj)≡(x,aj)(x,ai),1⩽i<j⩽n,(16)(∂in,ν(x),aj)≡{(x,aj),1⩽j<i⩽n,(x,aj+1),1⩽i⩽j⩽n-1,(17)(∂in,ν(x),1)=(x,1),1⩽i⩽n,ν∈{0,1},(18)(ϵin(x),aj)≡{(x,aj-1),1⩽i<j⩽n+1,(x,1),1⩽i=j⩽n+1,(x,aj),1⩽j<i⩽n+1.
The relation (15) follows from commutativity of {x}×ℕn. The relations (16) are obtained by the identifications:
(19)(∂in,ν(x),u)≡(x,H(δin,ν)(u)),∀n⩾1,1⩽i⩽n,ν∈{0,1},x∈Xn,u∈H(𝕀n-1).
The relations (18) can be obtained from
(20)(x,H(εin+1)u)≡(ϵin(x),u),∀x∈Xn,u∈ℕn+1
by the substitution u=aj.
Identity (neutral) elements in∐n⩾0‍∐x∈Xn‍(H(𝕀n))x are equal. It follows that (x,1)≡1 for all n⩾0 and x∈Xn.
Hence, the relations (17) can be removed leaving the (x,1)≡1.
It follows from(x,an)≡(∂n-1n,νx,an-1)≡⋯≡(∂12,ν⋯∂n-2n-1,ν∂n-1n,ν(x),a1) that each generator equals (γ,a1) for some γ∈X1. Moreover for dim(x)=n, for every 1⩽j⩽n, the similar sequence of relations leads to
(21)(x,aj)≡(∂12,ν⋯∂n-2n-1,ν∂n-1n,ν(x),a1).
Consequently, it is enough to leave the generators corresponding to 1-cubes. All relations can be obtained by the relations between those generators corresponding to 1-cubes.
It is easy to see that, among the relations (18), can be left only the following identifications (for i=j=1 and n=0):
(22)(x,1)≡(ϵ10(x),a1),∀x∈X0.
So,G(X) can be given by generators (x,a1), x∈X1. The class of (ϵ10,a1) equals 1. Since (∂22,ν(x),a1)≡(x,a1) and (∂12,ν(x),a1)≡(x,a2), every 2-cube (23) gives (∂22,0(x),a1)≡(∂22,1(x),a1), (∂12,0(x),a1)≡(∂12,1(x),a1),
(23)
We have the following relations between the generators,(24)(∂22,ν(x),a1)(∂12,ν(x),a1)≡(∂12,ν(x),a1)(∂22,ν(x),a1).
Since a1=a for all pairs (x1,a1) with x1∈X1, we can take the generators x1∈X1 instead of generators (x1,a1). Thus, we obtain the desired generators and relations. And the class of ϵ10(x)∈X1 equals 1.For example, the cubical set shown in (23) has the monoid G(X) isomorphic to the free commutative monoid generated by two elements.The category of generalized tori is the image of the functorT. By Proposition 7, that is, a full subcategory of Set□op we have shown that T has the left adjoint G. By [8, Theorem IV.3.1], reflectivity is equivalent to that the counit of adjunction is an isomorphism. Therefore, we have the following.Corollary 9.
The subcategory of generalized tori is reflective in the category of cubical sets. In particular, counit of the adjunctionεM(E,I):GTM(E,I)→M(E,I) is an isomorphism.


### 2.4. Independence Preserving Morphisms

We introduce independence preserving morphisms of cubical sets. We prove that the category of cubical sets and independence preserving morphisms are linked withFPCM∥ by adjoint functors.Definition 10.
A morphism of cubical setsφ:(X,∂in,ν,ϵin)→(Y,∂in,ν,ϵin) are independence preserving if
(25)(∀x∈X2),[∂12,0x]≠[∂22,0x],∂12,0x∉ϵ10(X0),∂22,0x∉ϵ10(X0)⟹[∂12,0φ(x)]≠[∂22,0φ(x)]∨((∂12,0φ(x)∈ϵ10(Y0)),(∂22,0φ(x)∈ϵ10(Y0))).Here,[x] denotes the congruence class of x∈X1 considered in Theorem 8.LetCube∥ denotes the category of cubical sets and independence preserving morphisms. We construct the adjoint functors between FPCM∥ and Cube∥. Definition 10 and Corollary 9 follow.Lemma 11.
LetT:FPCM→Set□op be the functor given in Definition 6 and let G:Set□op→FPCM be the left adjoint to T. (i)
A morphism of cubical setsφ:X→Y is independence preserving if and only if one is carried by the functor G to an independence preserving basic homomorphism Gφ:G(X)→G(Y).(ii)
Basic homomorphismf:M(E,I)→M(E′,I′) is carried by the functor T to independence preserving morpism if and only if it is independence preserving.(iii)
All componentsεM(E,I):GTM(E,I)→M(E,I) of the counit are independence preserving.(iv)
All componentsηX:X→TGX of the unit are independence preserving.Proof.
The property (i) follows from Definition10. Let us prove the last assertion. By Definition 10, it is equivalent to the statement that G(ηX):G(X)→G(T(G(X))) is independence preserving. Since G is left adjoint to T, the composition G(X)→G(ηX)G(T(G(X)))→εGXG(X) is equal to the identity morphism. The morphism G(T(G(X)))→εGXG(X) is isomorphism by Corollary 9. Consequently, G(ηX):G(X)→G(T(G(X))) is an isomorphism. Thus, ηX:X→T(G(X)) is independence preserving by (i).We obtain by Theorem8 and by Lemma 11 the following.Theorem 12.
Restrictions of the functorsG and T on the independence preserving morphisms give the adjoint functors
(26)
whereG∥ is left adjoint to T∥.


## 2.1. Preliminaries

Throughout the paper,Set denotes the category of sets and maps.For any category𝒜 and objects A,A′∈𝒜, let 𝒜(A,A′) denotes the set of morphisms f:A→A′. Let 𝒜op be the opposite category. Adiagram (of objects) in 𝒜 is any functor from some small category J to 𝒜. Let {D(j)}j∈J denotes a diagram D:J→𝒜. 𝒜J will always denote the category of diagrams J→𝒜 and natural trasformations between them.LetS:𝒞→𝒟 be a functor between small categories and let 𝒜 be an arbitrary category. Consider the functor (-)∘S:𝒜𝒟→𝒜𝒞 defined on objects as F↦F∘S and on morphisms as η↦η★S. Left derived functor LanS:𝒜𝒞→𝒜𝒟 to (-)∘S is called a left Kan extension alongS.LetY′:𝒟→Set𝒟op be the Yoneda functor described in [8, III.2, page 62]. For each functor H:𝒟→𝒜, we consider the functor D:𝒜→Set𝒟op defined on objects A∈𝒜 by its values D(A)(-)=𝒜(H(-),A) with the obvious extension to morphisms.Proposition 1 (see [9, Proposition II.1.3]).
Let𝒜 be a cocomplete category and let 𝒟 be a small category. For every functor H:𝒟→𝒜 the functor D:𝒜→Set𝒟op has a left adjoint functor isomorphic to the left Kan extension G=LanY′H:
(2)For anyX∈Set𝒟op, we have LanY′X=lim⟶𝒟↓X(H∘PX) where 𝒟↓X=Y′↓X denotes the comma category of objects Y′-over X for the Yoneda functor Y′:𝒟→Set□op and P=PX:𝒟↓X→𝒟 is the projection [8].We can obtain by the theory of ends [8, Theorem X.4.1, page 240] the following.Proposition 2 (see [8]).
For eachX∈Set𝒟op, G(X) equals the colimit of a diagram defined on a directed bipartite graph consisting of morphisms
(3)
where f:a→b runs all morphisms of the category 𝒟.


## 2.2. Trace Monoids

LetE be a set. A binary relation I⊆E×E is irreflexive if (∀a∈E)(a,a)∉I. One is symmetric if (∀(a,b)∈E×E)(a,b)∈I⇒(b,a)∈I. An independence relation on E is an arbitrary irreflexive symmetric binary relation I⊆E×E. In this case, elements a,b∈E are independent if (a,b)∈I.LetE* be the set of all words  a1a2⋯an composed of lettersa1,a2,…,an∈E for all n⩾0. Then, E* is the monoid with the operation of concatenation by the following formula:
(4)(a1⋯an)(b1⋯bm)=a1⋯anb1⋯bm.Identity element1 is the empty word.LetI be an independence relation on E. Define an equivalence relation ≡I on E* assuming w1≡w2 if the word w2 can be obtained from w1 by a finite sequence permutations of adjacent independent elements. For any w∈E*, its equivalence class [w] is called a trace. It is easy to see that the operation [w1][w2]=[w1w2] transforms the set of equivalence classes E*/≡ in a monoid. This monoid is called a trace monoidM(E,I).Our definition of trace monoid is different from that given in [10]. We suppose that E can be infinite.In some cases, we omit square brackets and writew∈M(E,I) instead of [w]∈M(E,I). If I=∅, then M(E,I) is the free monoidE*. If I=((E×E)∖{(a,a)∣a∈E}), then M(E,I) is the free commutative monoid ℕ(E).Definition 3.
A homomorphismf:M(E,I)→M(E′,I′) is basic if f(E)⊆E′∪{1}.Ifw=e1⋯en∈M(E,I) for some e1∈E,…,en∈E, then n is the length of trace w.Proposition 4.
Every diagramD:J→FPCM has the colimit in FPCM.Proof.
LetD(j)=M(Ej,Ij) for j∈J and let ∐j∈J‍D(j) be the coproduct in the category of monoids Mon. Then, the colimit lim⟶J{D(j)}j∈J is equal to the quotient monoid ∐j∈J‍M(Ej,Ij)/≡I where ≡I is the smallest congruence relation satisfying e≡ID(i→αj)(e) for all i∈J, j∈J, α∈J(i,j), e∈Ei. A more detailed proof can be found in the preprint [11].Definition 5.
A basic homomorphismf:M(E,I)→M(E′,I′) is independence preserving if for all a,b∈E the following implication holds:
(5)(a,b)∈I⟹(f(a)≠f(b))∨(f(a)=f(b)=1).This is equivalent to the following condition:(6)(a,b)∈I⟹(f(a),f(b))∈I′∨f(a)=1∨f(b)=1.It follows that the composition of independence preserving homomorphisms is independence preserving. LetFPCM∥⊂FPCM be a subcategory consisting of all trace monoids and basic independence preserving homomorphisms.


## 2.3. Cubical Sets and Trace Monoids

Acubical set(Xn,∂in,ν,ϵin) is a sequence of sets Xn, n∈ℕ with two family of maps(i)
∂in,ν:Xn→Xn-1, 1⩽i⩽n, ν∈{0,1}, (face operators)(ii)
ϵin:Xn→Xn+1, 1⩽i⩽n+1, (degeneracies)satisfying the following equations:(7)∂in-1,α∂jn,β=∂j-1n-1,β∂in,α,2⩽i<j⩽n,ϵin+1ϵjn=ϵj+1n+1ϵin,1⩽i⩽j⩽n+1,∂in+1,αϵjn={ϵj-1n-1∂in,α,1⩽i<j⩽n+1,ϵjn-1∂i-1n,α,1⩽j<i⩽n+1,1Xn,i=j.Amorphismf:X→Yof cubical sets is a family of maps fn:Xn→Yn commuting with the face operators and degeneracies. Let Cube be a category of cubical sets and morphisms.Let□ be the category consisting of the partially ordered sets 𝕀n={0,1}n and maps admitting decompositions by the following maps:
(8)δin,ν(x1,…,xn)=(x1,…,xi-1,ν,xi,…,xn),εin(x1,…,xn)=(x1,…,xi-1,xi+1,…xn).By settingX(𝕀n)=Xn, X(δin,ε)=∂in,ε, X(εin)=ϵin, we can consider every cubical set as functor □op→Set. A morphism of cubical sets can be considered as natural transformations. We will identify the category Cube with Set□op.Introduce generalized tori.Definition 6.
LetM(E,I) be a trace monoid. Generalized torusTM(E,I) is a cubical set consisting of sets T0M(E,I)={1} and
(9)TnM(E,I)={eiej=ejei∀1⩽i<j⩽n}(e1,…,en)∣ei∈E∪{1}∀1⩽i⩽n,eiej=ejei∀1⩽i<j⩽n}
for all n⩾1. The maps ∂in,ν, ϵin are defined by
(10)∂in,ν(e1,…,en)=(e1,…,ei-1,ei+1,…,en),ϵin(e1,…,en)=(e1,…,ei-1,1,ei,…,en).The mapM(E,I)↦TM(E,I) extends to a functor T:FPCM→Set□op which assigns to each basic homomorphism f:M(E,I)→M(E′,I′) a morphism of cubical sets given by a family of maps Tnf:TnM(E,I)→TnM(E′,I′) defined as
(11)Tnf(e1,…,en)=(f(e1),…,f(en)).
And conversely, since every morphism of cubical sets commutes with face operators, any morphism ηn:TnM(E,I)→TnM(E′,I′) can be given by the maps (e1,…,en)↦(η1(e1),…,η1(en)) defined by some η1:E→E′∪{1}. So, it holds the following.Proposition 7.
The functorT:FPCM→Set□op is full and faithful.We will prove the following.Theorem 8.
The functorT:FPCM→Set□op has a left adjoint G:Set□op→FPCM. For every cubical set X, the trace monoid G(X) can be given by the generator set X1/≡ by a smallest equivalence relation on X1 identifying ∂i2,0x2≡∂i2,1x2 for all x2∈X2 and i∈{1,2}, with the following relations for the equivalence classes:
(12)[∂12,0x2][∂22,0x2]=[∂22,0x2][∂12,0x2],∀x2∈X2,[ϵ10(x0)]=1,∀x0∈X0.Proof.
For the construction of left adjoint toT, we use Propositions 1 and 2. With this aim, define a functor H:□→FPCM by setting H(𝕀n)=ℕn on objects of □. Let H(δin,ν)(ak1,…,akn)=(ak1,…,aki-1,1,aki,…,akn) for all 1⩽i⩽n and ε∈{0,1}. Set H(εin):ℕn→ℕn-1 by
(13)H(εin)(ak1,…,akn)=(ak1,…,aki-1,aki+1,…,akn).
Here, ak∈ℕ are elements of the free monoid generated by one element ℕ={1,a,a2,…}. Let ai∈ℕn be the tuple (1,…,1,a,1,…,1) in which the generator a is located on the ith place. In particular, a1=(a,1,…,1).
Basic homomorphismsℕn→M(E,I) are given by values at ai, 1⩽i⩽n. Therefore, FPCM(ℕn,M(E,I))≅TnM(E,I). It follows that the functor T is isomorphic to D acting by D(M)=FPCM(H(-),M):□op→Set. Hence, the functor T has a left adjoint G.
By Proposition2, the object G(X) is isomorphic to quotient monoid of ∐n⩾0,x∈Xn‍(H(𝕀n))x by the smallest congruence relation identificating the pairs:
(14)(x,H(f)(u))≡(X(f)(x),u),∀f∈(𝕀m,𝕀n),u∈H(𝕀m),x∈Xn.
Element u∈ℕm equals (ak1,…,akm) for some nonnegative integers ki.
Substitutingf by δin-1,ν and εin+1 and using the commutativity of monoids {x}×ℕn, we conclude that monoid G(X) can be given by the generators (x,aj) with the relations
(15)(x,ai)(x,aj)≡(x,aj)(x,ai),1⩽i<j⩽n,(16)(∂in,ν(x),aj)≡{(x,aj),1⩽j<i⩽n,(x,aj+1),1⩽i⩽j⩽n-1,(17)(∂in,ν(x),1)=(x,1),1⩽i⩽n,ν∈{0,1},(18)(ϵin(x),aj)≡{(x,aj-1),1⩽i<j⩽n+1,(x,1),1⩽i=j⩽n+1,(x,aj),1⩽j<i⩽n+1.
The relation (15) follows from commutativity of {x}×ℕn. The relations (16) are obtained by the identifications:
(19)(∂in,ν(x),u)≡(x,H(δin,ν)(u)),∀n⩾1,1⩽i⩽n,ν∈{0,1},x∈Xn,u∈H(𝕀n-1).
The relations (18) can be obtained from
(20)(x,H(εin+1)u)≡(ϵin(x),u),∀x∈Xn,u∈ℕn+1
by the substitution u=aj.
Identity (neutral) elements in∐n⩾0‍∐x∈Xn‍(H(𝕀n))x are equal. It follows that (x,1)≡1 for all n⩾0 and x∈Xn.
Hence, the relations (17) can be removed leaving the (x,1)≡1.
It follows from(x,an)≡(∂n-1n,νx,an-1)≡⋯≡(∂12,ν⋯∂n-2n-1,ν∂n-1n,ν(x),a1) that each generator equals (γ,a1) for some γ∈X1. Moreover for dim(x)=n, for every 1⩽j⩽n, the similar sequence of relations leads to
(21)(x,aj)≡(∂12,ν⋯∂n-2n-1,ν∂n-1n,ν(x),a1).
Consequently, it is enough to leave the generators corresponding to 1-cubes. All relations can be obtained by the relations between those generators corresponding to 1-cubes.
It is easy to see that, among the relations (18), can be left only the following identifications (for i=j=1 and n=0):
(22)(x,1)≡(ϵ10(x),a1),∀x∈X0.
So,G(X) can be given by generators (x,a1), x∈X1. The class of (ϵ10,a1) equals 1. Since (∂22,ν(x),a1)≡(x,a1) and (∂12,ν(x),a1)≡(x,a2), every 2-cube (23) gives (∂22,0(x),a1)≡(∂22,1(x),a1), (∂12,0(x),a1)≡(∂12,1(x),a1),
(23)
We have the following relations between the generators,(24)(∂22,ν(x),a1)(∂12,ν(x),a1)≡(∂12,ν(x),a1)(∂22,ν(x),a1).
Since a1=a for all pairs (x1,a1) with x1∈X1, we can take the generators x1∈X1 instead of generators (x1,a1). Thus, we obtain the desired generators and relations. And the class of ϵ10(x)∈X1 equals 1.For example, the cubical set shown in (23) has the monoid G(X) isomorphic to the free commutative monoid generated by two elements.The category of generalized tori is the image of the functorT. By Proposition 7, that is, a full subcategory of Set□op we have shown that T has the left adjoint G. By [8, Theorem IV.3.1], reflectivity is equivalent to that the counit of adjunction is an isomorphism. Therefore, we have the following.Corollary 9.
The subcategory of generalized tori is reflective in the category of cubical sets. In particular, counit of the adjunctionεM(E,I):GTM(E,I)→M(E,I) is an isomorphism.


## 2.4. Independence Preserving Morphisms

We introduce independence preserving morphisms of cubical sets. We prove that the category of cubical sets and independence preserving morphisms are linked withFPCM∥ by adjoint functors.Definition 10.
A morphism of cubical setsφ:(X,∂in,ν,ϵin)→(Y,∂in,ν,ϵin) are independence preserving if
(25)(∀x∈X2),[∂12,0x]≠[∂22,0x],∂12,0x∉ϵ10(X0),∂22,0x∉ϵ10(X0)⟹[∂12,0φ(x)]≠[∂22,0φ(x)]∨((∂12,0φ(x)∈ϵ10(Y0)),(∂22,0φ(x)∈ϵ10(Y0))).Here,[x] denotes the congruence class of x∈X1 considered in Theorem 8.LetCube∥ denotes the category of cubical sets and independence preserving morphisms. We construct the adjoint functors between FPCM∥ and Cube∥. Definition 10 and Corollary 9 follow.Lemma 11.
LetT:FPCM→Set□op be the functor given in Definition 6 and let G:Set□op→FPCM be the left adjoint to T. (i)
A morphism of cubical setsφ:X→Y is independence preserving if and only if one is carried by the functor G to an independence preserving basic homomorphism Gφ:G(X)→G(Y).(ii)
Basic homomorphismf:M(E,I)→M(E′,I′) is carried by the functor T to independence preserving morpism if and only if it is independence preserving.(iii)
All componentsεM(E,I):GTM(E,I)→M(E,I) of the counit are independence preserving.(iv)
All componentsηX:X→TGX of the unit are independence preserving.Proof.
The property (i) follows from Definition10. Let us prove the last assertion. By Definition 10, it is equivalent to the statement that G(ηX):G(X)→G(T(G(X))) is independence preserving. Since G is left adjoint to T, the composition G(X)→G(ηX)G(T(G(X)))→εGXG(X) is equal to the identity morphism. The morphism G(T(G(X)))→εGXG(X) is isomorphism by Corollary 9. Consequently, G(ηX):G(X)→G(T(G(X))) is an isomorphism. Thus, ηX:X→T(G(X)) is independence preserving by (i).We obtain by Theorem8 and by Lemma 11 the following.Theorem 12.
Restrictions of the functorsG and T on the independence preserving morphisms give the adjoint functors
(26)
whereG∥ is left adjoint to T∥.


## 3. Category of Trace Monoid Actions

We construct adjoint functors between a category of monoids acting on sets and the category of cubical sets.


### 3.1. Trace Monoid Actions

Definition 13.
A trace monoid action(M(E,I),X) consists of a trace monoid M(E,I) with a set X and a map X×M(E,I)→·X called a right action, (x,μ)↦x·μ, satysfying to the following conditions:(i)
(∀x∈X)(∀μ1,μ2∈M(E,I))(x·μ1)·μ2=x·(μ1μ2),(ii)
(∀x∈X)x·1=x.For example, for any trace monoidM(E,I), we have the trace monoid action (M(E,I),M(E,I)) defined as x·μ=xμ for all x,μ∈M(E,I). It is called the action by right translations.Definition 14.
Amorphism(f,σ):(M(E,I),X)→(M(E′,I′),X′) of trace monoid actions consists of a homomorphism f:M(E,I)→M(E′,I′) and a map σ:X→X′ such those
(27)(∀x∈X)(∀μ∈M(E,I))σ(x·μ)=σ(x)·f(μ).For example, for any homomorphismf:M(E,I)→M(E′,I′), the pair (f,f):(M(E,I),M(E,I))→(M(E′,I′),M(E′,I′)) is the morphism as satifying f(x·μ)=f(x)f(μ).A morphism(f,σ):(M(E,I),X)→(M(E′,I′),X′) of trace monoid actions is basic if f is a basic homomorphism. It is called independence preserving if f is independence preserving.Let(FPCM,Set) be a category of trace monoid actions and basic morphisms.Lemma 15.
The category(FPCM,Set) is cocomplete.Proof.
Monoid is a category with unique object. A monoid action(M,X) can be considered as a functor X~:Mop→Set with the value X on the unique object of the category M. X~ assigns to morphisms μ∈M the maps X→X such those X~(μ)(x)=x·μ. The following natural transformations σ~:X~→X~′∘fop corresponds to morphisms (f,σ):(M,X)→(M′,X′):
(28)
Consider an arbitrary diagram{(M(Ei,Ii),Xi)}i∈J in (FPCM,Set) as the diagram of functors X~i:M(Ei,Ii)op→Set. There exists lim⟶J{M(Ei,Ii)} in the category FPCM. Let {λi}i∈J be the colimit cone. Take left Kan extensions LanλiopX~i belonging to the category of functors from lim⟶J{M(Ei,Ii)}op to Set. It is easy to see that desired colimit equals (lim⟶J{M(Ei,Ii)},lim⟶J{LanλiopX~i}).We study colimits in the category(FPCM,Set) for diagrams of trace monoid actions by right translations. For an arbitrary small category, J, π0(J) denotes the set of connected components of J. For a set S, (M(E,I),M(E,I)×S) denotes a trace monoid with the action by right translations(x,s)·μ=def(x·μ,s) for all x,μ∈M(E,I), s∈S.Let{M(Ei,Ii)}i∈J be a diagram of trace monoids and basic homomorphisms Mα:M(Ei,Ii)→M(Ej,Ij) defined for all i,j∈Ob(J) and α∈J(i,j). Then, we have the diagram of trace monoid actions {(M(Ei,Ii),M(Ei,Ii))}i∈J by right translations, consisting of morphisms (Mα,Mα).Proposition 16.
lim
⟶
J
{
(
M
(
E
i
,
I
i
)
,
M
(
E
i
,
I
i
)
)
}
i
∈
J is isomorphic to the trace monoid action (lim⟶J{M(Ej,Ij)},lim⟶J{M(Ej,Ij)}×π0(J)) by right translations.Proof.
M
i will denote M(Ei,Ii). Let λi:Mi→lim⟶J{Mi}i∈I be the colimit cone. We prove the universality of the cone of morphisms (Mi,Mi)⟶(λi,(λi,cls(i))(lim⟶J{Mi},lim⟶J{Mi}×π0(J)) defined as
(29)(λi,(λi,cls(i)))(μi,ti)=(λi(μi),(λi(ti),cls(i)))
for all μi,ti∈Mi. Here, cls(i) is the connected components of J containing i∈Ob(J).
Consider an arbitrary cone(Mi,Mi)⟶(νi,ξi)(M(E,I),X) and construct a morphism (ν,ξ) making the following commutative diagram in (FPCM,Set):
(30)
The existence and uniqueness of the homomorphism ν follow from the universal property of lim⟶J{Mi} in FPCM.
Constructξ. Since (νi,ξi) is cone, ξi(1)=ξj(1) for all i,j with same connected components. It follows that, for every c∈π0(J), the values ξ(1,c)=ξi(1) must be determined by an arbitrary object i belonging to connected component c. These values give the unique extension ξ(μ,c)=ξ((1,c)·μ)=ξ(1,c)·ν(μ) to the set lim⟶J{Mi}×π0(J). It follows the uniqueness of ξ. The equality of values ξ(λi,cls(i))(1)=ξi(1) at 1∈Mi gives coincidence of compositions ξ∘(λi,cls(i))=ξi for all i∈Ob(J) and with it is the commutative triangles (30).Further, letG:Set□op→FPCM, T:FPCM→Set□op, H:□→FPCM denote the functors involved in Theorem 8. Let Q:(FPCM,Set)→Set□op be the functor assigning to every trace monoid action (M(E,I),S) the cubical set
(31)Qn(M(E,I),S)={eiej=ejei∀1≤i<j≤n}(s,e1,…,en):s∈S,(∀i∈{1,…,n})ei∈E∪{1},eiej=ejei∀1⩽i<j⩽n}.Recall that□↓X denotes the comma category Y′↓X of objects Y′-over X (Proposition 1).Theorem 17.
The functorQ:(FPCM,Set)→Set□op has a left adjoint G′:Set□op→(FPCM,Set) such that G′(X)=(G(X),G(X)×π0(□↓X)) are the trace monoid actions by right translation for all cubical sets X.Proof.
LetH′:□→(FPCM,Set) be a functor defined as H′(𝕀n)=(ℕn,ℕn) (with actions by right translations) at objects and H′(f)=(H(f),H(f)) for morphisms f∈Mor(□). The category (FPCM,Set) is cocomplete. Hence, this functor fits into the diagram
(32)
where G′ is left adjoint to Q′ taking values
(33)Q′(M(E,I),S)(𝕀n)=(FPCM,Set)(H′(𝕀n),(M(E,I),S)).
Elements (f,σ)∈(FPCM,Set)(H′(𝕀n),(M(E,I),S)) are determined by values σ(1)∈S where 1 is identity element of the monoid ℕn and by the values of f on generators of the monoid ℕn. It follows that the functors Q′ and Q are isomorphic. For X∈Set□op, G′(X) is the colimit of a diagram consisting of trace monoids with actions by right translations (H(𝕀n),H(𝕀n)). The colimit in the first component equals G(X) by Theorem 8. We obtain G′(X)=(G(X),G(X)×π0(□↓X)) by Proposition 16.


### 3.2. Independent Morphisms of Trace Monoid Actions

By Lemma11, a morphism of cubical set φ:X→Y is independence preserving if and only if the homomorphism of monoids Gφ:GX→GY is independence preserving.Definition 18.
A morphism(f,σ):((M(E,I),S)→(M(E′,I′),S′)) of the category (FPCM,Set) is independence preserving if f:M(E,I)→M(E′,I′) is independence preserving homomorphism.SinceG′X=(GX,GX×π0(□↓X)), it follows from this definition that φ:X→Y is independence preserving if and only if G′φ:G′X→G′Y is independence preserving. So, the functor G′ takes independence preserving morphisms into independence preserving.The same is true forQ.Lemma 19.
The functorQ:(FPCM,Set)→Set□op takes independence preserving morphisms into independence preserving.Proof.
By definition, a morphismQ(f,σ):Q(M(E,I),S)→Q(M(E′,I′),S′) is independence preserving if and only if the homomorphism of monoids GQ(f,σ):GQ(M(E,I),S)→GQ(M(E′,I′),S′) is independence preserving. The monoid GQ(M(E,I),S) is generated by classes [(s,e1)] such that [(s,e1)]=[(s·e,e1)] if (e,e1)∈I. We have also ϵ10(s)≡(s,1). Therefore, [(s,1)]=1. It follows that [(s,e)]=1 if and only if e=1. We need to prove the following implication:
(34)[(s,e1)][(s,e2)]=[(s,e2)][(s,e1)],[(s,e1)]≠[(s,e2)],[(s,e1)]≠1,[(s,e2)]≠1⟹[(σ(s),f(e1))]≠[(σ(s),f(e2))]∨([(σ(s),f(e1))]=[(σ(s),f(e2))]=1).
By the equivalences [(s,e)]≡1⇔e=1 in GQM(E,I) and [(s,e1)]≠[(s,e2)]⇔e1≠e2 in M(E,I), the premise of implication (34) is transformed into formula
(35)[(s,e1)][(s,e2)]=[(s,e2)][(s,e1)],e1≠e2,e1≠1,e2≠1.
Since the homomorphism f is independence preserving, we obtain the formula f(e1)≠f(e2)∨f(e1)=f(e2)=1 leading to the conclusion of (34).Lemma 20.
The unit of the adjunctionηX:X→QG′X is independence preserving.Proof.
SinceG′ is left adjoint to Q, the morphism G′X→G′(ηX)G′QG′X is a coretraction. It follows that the homomorphism of monoids GX→G(ηX)GQG′X is a coretraction. It takes independent elements in the not equal. Hence, GX→G(ηX)GQG′X is dependence preserving.Letε(M(E,I),S):G′Q(M(E,I),S)→(M(E,I),S) be the counit of adjunction G′⊣Q.Lemma 21.
The counit of adjunctionε(M(E,I),S) is independence preserving.Proof.
The morphismε(M(E,I),S) consists of some pair (f,σ). It is independence preserving if and only if the homomorphism f:GQ(M(E,I),S)→M(E,I) is independence preserving. The monoid GQ(M(E,I),S) is generated by classes [(s,e)] of 1-cubes (s,e)∈Q1(M(E,I),S)=S×E. The homomorphism f assigns to each class [(s,e)] the element e∈E. If [(s,e1)]≠[(s,e2)] and ([(s,e1)],[(s,e2)]) are independed, then e1≠e2. Hence, f is independence preserving.It follows from obtained Lemmas.Theorem 22.
The restrictions of functorsQ and G′ on the subcategories consisting of independence morphisms give adjoint functors
(36)


### 3.3. Asynchronous Systems and Higher Dimensional Automata

Ahigher dimensional automation(X,x0) consists of a cubical set X and an initial pointx0∈X0. A morphismf:(X,x0)→(X′,x0′)of higher dimensionalautomata is a morphism of cubical sets f:X→X′ such that f0(x0)=x0′. Let Cubep be the category of higher dimensional automata and let Cubep∥ be the category of higher dimensional automata and morphisms f:(X,x0)→(X′,x0′) for which f:X→X′ are independence preserving.Letpt be the cubical set such that ptn consists of unique element p for all n⩾0. Face operators and degeneracies are the identity maps.It is easy to see thatCubep∥≅pt↓Cube∥.Introduce a category of weak asynchronous systems. Consider partial maps of sets.For any setE, let E*=E⊔{*}. The set E* is called pointed. The element * is the same for all pointed sets. A map f:E1*→E2* is pointed if f(*)=*. Let Set* be the category of pointed sets and pointed maps.Any partial mapf:E1⇀E2 will be considered as the pointed map f*:E1*→E2* defined as follows:
(37)f*(a)={f(a),iff(a)isdefined,*,otherwise.
This allows us to identify the category of sets and partial maps with the category Set*.A(right) monoid action(M,S*)on a pointed set consists of a monoid M and a pointed set S* with an arbitrary map ·:S*×M→S* satisfying the following conditions:(i)
(∀s∈S*)(∀μ1,μ2∈M)(x·μ1)·μ2=x·(μ1μ2),(ii)
(∀x∈S*)x·1=x,(iii)
(∀μ∈M)*·μ=*.Let(M,S*) be a monoid action on a pointed set. Since the monoid is a category with an unique object, (M,S*) can be considered as a functor Mop→Set* assigning to the unique object the pointed set S* and assigning to morphisms μ∈M the pointed maps (M,S*)(μ):S*→S* such those (M,S*)(μ)(x)=x·μ.It was shown in [12] that each asynchronous system can be considered as a trace monoid action on a pointed set with an initial point.Definition 23.
A weak asynchronous system
(
M
(
E
,
I
)
,
S
*
,
s
0
) is a trace monoid action (M(E,I),S*) on a pointed set S* with an initial points0∈S*.If we requireS≠∅ and s0∈S, then we get the definition of an asynchronous system in the sense of Bednarczyk [1].Apolygonal morphism(f,σ):(M(E,I),S*,s0)→(M(E′,I′),S*′,s0′) of weak asynchronous systems is an independence preserving basic homomorphism f:M(E,I)→M(E′,I′) with a pointed map σ:S*→S* satisfying the following conditions:(i)
(∀s∈S*)(∀μ∈M(E,I))σ(s·μ=σ(s)·f(μ)),(ii)
σ(s0)=s0′.The mapf is pointed from where f(*)=*. Let 𝒜S♭ be the category of weak asynchronous systems and polygonal morphisms. Construct a functor W:𝒜S♭→Cubep∥ assigning to every asynchronous system (M(E,I),S*,s0) the cubical set consisting of a sequence of pointed sets
(38)Wn(M(E,I),S*,s0)={(s,e1,…,en)∣s∈S*,(e1,…,en)∈TnM(E,I)}
and W0(M(E,I),S*,s0)=S*. Face operators are defined as follows:
(39)∂in,ν(s,e1,…,en)=(s·eiν,e1,…,ei-1,ei+1,…,en).Degeneracies are defined byϵin(s,e1,…,en)=(s,e1,…,ei-1,1,ei,…,en). Initial point in W(M(E,I),S*,s0) equals s0∈S*.Theorem 24.
The functorW:𝒜S♭→Cubep∥ has a left adjoint G′′:Cubep∥→𝒜S♭.Proof.
LetU:Set*→Set be the functor forgetting the point * and let L:Set→Set* be the left adjoint to U adding the point *. Let U¯=(FPCM∥,U) be the functor (FPCM∥,Set*)→(FPCM∥,Set) assigning to every trace monoid action X:M(E,I)op→Set* the composition U∘X and assigning to morphisms X→ξX′∘fop the morphisms U*ξ. Similarly, we define the functor L¯:(FPCM∥,Set)→(FPCM∥,Set*). Let η:IdSet→U∘L be a unit and let ε:L∘U→IdSet* be a counit of adjunction L⊣U. Since the functor L is left adjoint to U, the compositions U→η*UU∘L∘U→U*εU and L→L*ηL∘U∘L→ε*LL are equal to identity natural transformations. Construct natural transformations η¯:Id(FPCM∥,Set)→U¯∘L¯ and ε¯:L¯∘U¯→Id(FPCM∥,Set*) as follows: η¯X=η*X, ε¯X=ε*X. Components of natural transformations U¯→η¯*U¯U¯∘L¯∘U¯→U¯*ε¯U¯ and L¯→L¯*η¯L¯∘U¯∘L¯→ε¯*L¯L¯ on objects equal identity natural transformations. Therefore, L¯ is left adjoint to U¯.
Consider the compositions(40)where G′ and Q are the adjoint functors from Theorem 22. The functor L¯∘G′ is left adjoint to Q∘U¯.
The monoid{1} has the unique action on the set {p,*}. This trace monoid action equals L¯(G′(pt)). We have the adjoint functors between comma categories(41)
It easy to see that the category({p,*},{1})↓(FPCM∥,Set*) is isomorphic to 𝒜S♭. The composition of this isomorphism with Q∘U¯ is equal to the functor W. We obtain from this the functor L¯∘G′ left adjoint to W.


## 3.1. Trace Monoid Actions

Definition 13.
A trace monoid action(M(E,I),X) consists of a trace monoid M(E,I) with a set X and a map X×M(E,I)→·X called a right action, (x,μ)↦x·μ, satysfying to the following conditions:(i)
(∀x∈X)(∀μ1,μ2∈M(E,I))(x·μ1)·μ2=x·(μ1μ2),(ii)
(∀x∈X)x·1=x.For example, for any trace monoidM(E,I), we have the trace monoid action (M(E,I),M(E,I)) defined as x·μ=xμ for all x,μ∈M(E,I). It is called the action by right translations.Definition 14.
Amorphism(f,σ):(M(E,I),X)→(M(E′,I′),X′) of trace monoid actions consists of a homomorphism f:M(E,I)→M(E′,I′) and a map σ:X→X′ such those
(27)(∀x∈X)(∀μ∈M(E,I))σ(x·μ)=σ(x)·f(μ).For example, for any homomorphismf:M(E,I)→M(E′,I′), the pair (f,f):(M(E,I),M(E,I))→(M(E′,I′),M(E′,I′)) is the morphism as satifying f(x·μ)=f(x)f(μ).A morphism(f,σ):(M(E,I),X)→(M(E′,I′),X′) of trace monoid actions is basic if f is a basic homomorphism. It is called independence preserving if f is independence preserving.Let(FPCM,Set) be a category of trace monoid actions and basic morphisms.Lemma 15.
The category(FPCM,Set) is cocomplete.Proof.
Monoid is a category with unique object. A monoid action(M,X) can be considered as a functor X~:Mop→Set with the value X on the unique object of the category M. X~ assigns to morphisms μ∈M the maps X→X such those X~(μ)(x)=x·μ. The following natural transformations σ~:X~→X~′∘fop corresponds to morphisms (f,σ):(M,X)→(M′,X′):
(28)
Consider an arbitrary diagram{(M(Ei,Ii),Xi)}i∈J in (FPCM,Set) as the diagram of functors X~i:M(Ei,Ii)op→Set. There exists lim⟶J{M(Ei,Ii)} in the category FPCM. Let {λi}i∈J be the colimit cone. Take left Kan extensions LanλiopX~i belonging to the category of functors from lim⟶J{M(Ei,Ii)}op to Set. It is easy to see that desired colimit equals (lim⟶J{M(Ei,Ii)},lim⟶J{LanλiopX~i}).We study colimits in the category(FPCM,Set) for diagrams of trace monoid actions by right translations. For an arbitrary small category, J, π0(J) denotes the set of connected components of J. For a set S, (M(E,I),M(E,I)×S) denotes a trace monoid with the action by right translations(x,s)·μ=def(x·μ,s) for all x,μ∈M(E,I), s∈S.Let{M(Ei,Ii)}i∈J be a diagram of trace monoids and basic homomorphisms Mα:M(Ei,Ii)→M(Ej,Ij) defined for all i,j∈Ob(J) and α∈J(i,j). Then, we have the diagram of trace monoid actions {(M(Ei,Ii),M(Ei,Ii))}i∈J by right translations, consisting of morphisms (Mα,Mα).Proposition 16.
lim
⟶
J
{
(
M
(
E
i
,
I
i
)
,
M
(
E
i
,
I
i
)
)
}
i
∈
J is isomorphic to the trace monoid action (lim⟶J{M(Ej,Ij)},lim⟶J{M(Ej,Ij)}×π0(J)) by right translations.Proof.
M
i will denote M(Ei,Ii). Let λi:Mi→lim⟶J{Mi}i∈I be the colimit cone. We prove the universality of the cone of morphisms (Mi,Mi)⟶(λi,(λi,cls(i))(lim⟶J{Mi},lim⟶J{Mi}×π0(J)) defined as
(29)(λi,(λi,cls(i)))(μi,ti)=(λi(μi),(λi(ti),cls(i)))
for all μi,ti∈Mi. Here, cls(i) is the connected components of J containing i∈Ob(J).
Consider an arbitrary cone(Mi,Mi)⟶(νi,ξi)(M(E,I),X) and construct a morphism (ν,ξ) making the following commutative diagram in (FPCM,Set):
(30)
The existence and uniqueness of the homomorphism ν follow from the universal property of lim⟶J{Mi} in FPCM.
Constructξ. Since (νi,ξi) is cone, ξi(1)=ξj(1) for all i,j with same connected components. It follows that, for every c∈π0(J), the values ξ(1,c)=ξi(1) must be determined by an arbitrary object i belonging to connected component c. These values give the unique extension ξ(μ,c)=ξ((1,c)·μ)=ξ(1,c)·ν(μ) to the set lim⟶J{Mi}×π0(J). It follows the uniqueness of ξ. The equality of values ξ(λi,cls(i))(1)=ξi(1) at 1∈Mi gives coincidence of compositions ξ∘(λi,cls(i))=ξi for all i∈Ob(J) and with it is the commutative triangles (30).Further, letG:Set□op→FPCM, T:FPCM→Set□op, H:□→FPCM denote the functors involved in Theorem 8. Let Q:(FPCM,Set)→Set□op be the functor assigning to every trace monoid action (M(E,I),S) the cubical set
(31)Qn(M(E,I),S)={eiej=ejei∀1≤i<j≤n}(s,e1,…,en):s∈S,(∀i∈{1,…,n})ei∈E∪{1},eiej=ejei∀1⩽i<j⩽n}.Recall that□↓X denotes the comma category Y′↓X of objects Y′-over X (Proposition 1).Theorem 17.
The functorQ:(FPCM,Set)→Set□op has a left adjoint G′:Set□op→(FPCM,Set) such that G′(X)=(G(X),G(X)×π0(□↓X)) are the trace monoid actions by right translation for all cubical sets X.Proof.
LetH′:□→(FPCM,Set) be a functor defined as H′(𝕀n)=(ℕn,ℕn) (with actions by right translations) at objects and H′(f)=(H(f),H(f)) for morphisms f∈Mor(□). The category (FPCM,Set) is cocomplete. Hence, this functor fits into the diagram
(32)
where G′ is left adjoint to Q′ taking values
(33)Q′(M(E,I),S)(𝕀n)=(FPCM,Set)(H′(𝕀n),(M(E,I),S)).
Elements (f,σ)∈(FPCM,Set)(H′(𝕀n),(M(E,I),S)) are determined by values σ(1)∈S where 1 is identity element of the monoid ℕn and by the values of f on generators of the monoid ℕn. It follows that the functors Q′ and Q are isomorphic. For X∈Set□op, G′(X) is the colimit of a diagram consisting of trace monoids with actions by right translations (H(𝕀n),H(𝕀n)). The colimit in the first component equals G(X) by Theorem 8. We obtain G′(X)=(G(X),G(X)×π0(□↓X)) by Proposition 16.


## 3.2. Independent Morphisms of Trace Monoid Actions

By Lemma11, a morphism of cubical set φ:X→Y is independence preserving if and only if the homomorphism of monoids Gφ:GX→GY is independence preserving.Definition 18.
A morphism(f,σ):((M(E,I),S)→(M(E′,I′),S′)) of the category (FPCM,Set) is independence preserving if f:M(E,I)→M(E′,I′) is independence preserving homomorphism.SinceG′X=(GX,GX×π0(□↓X)), it follows from this definition that φ:X→Y is independence preserving if and only if G′φ:G′X→G′Y is independence preserving. So, the functor G′ takes independence preserving morphisms into independence preserving.The same is true forQ.Lemma 19.
The functorQ:(FPCM,Set)→Set□op takes independence preserving morphisms into independence preserving.Proof.
By definition, a morphismQ(f,σ):Q(M(E,I),S)→Q(M(E′,I′),S′) is independence preserving if and only if the homomorphism of monoids GQ(f,σ):GQ(M(E,I),S)→GQ(M(E′,I′),S′) is independence preserving. The monoid GQ(M(E,I),S) is generated by classes [(s,e1)] such that [(s,e1)]=[(s·e,e1)] if (e,e1)∈I. We have also ϵ10(s)≡(s,1). Therefore, [(s,1)]=1. It follows that [(s,e)]=1 if and only if e=1. We need to prove the following implication:
(34)[(s,e1)][(s,e2)]=[(s,e2)][(s,e1)],[(s,e1)]≠[(s,e2)],[(s,e1)]≠1,[(s,e2)]≠1⟹[(σ(s),f(e1))]≠[(σ(s),f(e2))]∨([(σ(s),f(e1))]=[(σ(s),f(e2))]=1).
By the equivalences [(s,e)]≡1⇔e=1 in GQM(E,I) and [(s,e1)]≠[(s,e2)]⇔e1≠e2 in M(E,I), the premise of implication (34) is transformed into formula
(35)[(s,e1)][(s,e2)]=[(s,e2)][(s,e1)],e1≠e2,e1≠1,e2≠1.
Since the homomorphism f is independence preserving, we obtain the formula f(e1)≠f(e2)∨f(e1)=f(e2)=1 leading to the conclusion of (34).Lemma 20.
The unit of the adjunctionηX:X→QG′X is independence preserving.Proof.
SinceG′ is left adjoint to Q, the morphism G′X→G′(ηX)G′QG′X is a coretraction. It follows that the homomorphism of monoids GX→G(ηX)GQG′X is a coretraction. It takes independent elements in the not equal. Hence, GX→G(ηX)GQG′X is dependence preserving.Letε(M(E,I),S):G′Q(M(E,I),S)→(M(E,I),S) be the counit of adjunction G′⊣Q.Lemma 21.
The counit of adjunctionε(M(E,I),S) is independence preserving.Proof.
The morphismε(M(E,I),S) consists of some pair (f,σ). It is independence preserving if and only if the homomorphism f:GQ(M(E,I),S)→M(E,I) is independence preserving. The monoid GQ(M(E,I),S) is generated by classes [(s,e)] of 1-cubes (s,e)∈Q1(M(E,I),S)=S×E. The homomorphism f assigns to each class [(s,e)] the element e∈E. If [(s,e1)]≠[(s,e2)] and ([(s,e1)],[(s,e2)]) are independed, then e1≠e2. Hence, f is independence preserving.It follows from obtained Lemmas.Theorem 22.
The restrictions of functorsQ and G′ on the subcategories consisting of independence morphisms give adjoint functors
(36)


## 3.3. Asynchronous Systems and Higher Dimensional Automata

Ahigher dimensional automation(X,x0) consists of a cubical set X and an initial pointx0∈X0. A morphismf:(X,x0)→(X′,x0′)of higher dimensionalautomata is a morphism of cubical sets f:X→X′ such that f0(x0)=x0′. Let Cubep be the category of higher dimensional automata and let Cubep∥ be the category of higher dimensional automata and morphisms f:(X,x0)→(X′,x0′) for which f:X→X′ are independence preserving.Letpt be the cubical set such that ptn consists of unique element p for all n⩾0. Face operators and degeneracies are the identity maps.It is easy to see thatCubep∥≅pt↓Cube∥.Introduce a category of weak asynchronous systems. Consider partial maps of sets.For any setE, let E*=E⊔{*}. The set E* is called pointed. The element * is the same for all pointed sets. A map f:E1*→E2* is pointed if f(*)=*. Let Set* be the category of pointed sets and pointed maps.Any partial mapf:E1⇀E2 will be considered as the pointed map f*:E1*→E2* defined as follows:
(37)f*(a)={f(a),iff(a)isdefined,*,otherwise.
This allows us to identify the category of sets and partial maps with the category Set*.A(right) monoid action(M,S*)on a pointed set consists of a monoid M and a pointed set S* with an arbitrary map ·:S*×M→S* satisfying the following conditions:(i)
(∀s∈S*)(∀μ1,μ2∈M)(x·μ1)·μ2=x·(μ1μ2),(ii)
(∀x∈S*)x·1=x,(iii)
(∀μ∈M)*·μ=*.Let(M,S*) be a monoid action on a pointed set. Since the monoid is a category with an unique object, (M,S*) can be considered as a functor Mop→Set* assigning to the unique object the pointed set S* and assigning to morphisms μ∈M the pointed maps (M,S*)(μ):S*→S* such those (M,S*)(μ)(x)=x·μ.It was shown in [12] that each asynchronous system can be considered as a trace monoid action on a pointed set with an initial point.Definition 23.
A weak asynchronous system
(
M
(
E
,
I
)
,
S
*
,
s
0
) is a trace monoid action (M(E,I),S*) on a pointed set S* with an initial points0∈S*.If we requireS≠∅ and s0∈S, then we get the definition of an asynchronous system in the sense of Bednarczyk [1].Apolygonal morphism(f,σ):(M(E,I),S*,s0)→(M(E′,I′),S*′,s0′) of weak asynchronous systems is an independence preserving basic homomorphism f:M(E,I)→M(E′,I′) with a pointed map σ:S*→S* satisfying the following conditions:(i)
(∀s∈S*)(∀μ∈M(E,I))σ(s·μ=σ(s)·f(μ)),(ii)
σ(s0)=s0′.The mapf is pointed from where f(*)=*. Let 𝒜S♭ be the category of weak asynchronous systems and polygonal morphisms. Construct a functor W:𝒜S♭→Cubep∥ assigning to every asynchronous system (M(E,I),S*,s0) the cubical set consisting of a sequence of pointed sets
(38)Wn(M(E,I),S*,s0)={(s,e1,…,en)∣s∈S*,(e1,…,en)∈TnM(E,I)}
and W0(M(E,I),S*,s0)=S*. Face operators are defined as follows:
(39)∂in,ν(s,e1,…,en)=(s·eiν,e1,…,ei-1,ei+1,…,en).Degeneracies are defined byϵin(s,e1,…,en)=(s,e1,…,ei-1,1,ei,…,en). Initial point in W(M(E,I),S*,s0) equals s0∈S*.Theorem 24.
The functorW:𝒜S♭→Cubep∥ has a left adjoint G′′:Cubep∥→𝒜S♭.Proof.
LetU:Set*→Set be the functor forgetting the point * and let L:Set→Set* be the left adjoint to U adding the point *. Let U¯=(FPCM∥,U) be the functor (FPCM∥,Set*)→(FPCM∥,Set) assigning to every trace monoid action X:M(E,I)op→Set* the composition U∘X and assigning to morphisms X→ξX′∘fop the morphisms U*ξ. Similarly, we define the functor L¯:(FPCM∥,Set)→(FPCM∥,Set*). Let η:IdSet→U∘L be a unit and let ε:L∘U→IdSet* be a counit of adjunction L⊣U. Since the functor L is left adjoint to U, the compositions U→η*UU∘L∘U→U*εU and L→L*ηL∘U∘L→ε*LL are equal to identity natural transformations. Construct natural transformations η¯:Id(FPCM∥,Set)→U¯∘L¯ and ε¯:L¯∘U¯→Id(FPCM∥,Set*) as follows: η¯X=η*X, ε¯X=ε*X. Components of natural transformations U¯→η¯*U¯U¯∘L¯∘U¯→U¯*ε¯U¯ and L¯→L¯*η¯L¯∘U¯∘L¯→ε¯*L¯L¯ on objects equal identity natural transformations. Therefore, L¯ is left adjoint to U¯.
Consider the compositions(40)where G′ and Q are the adjoint functors from Theorem 22. The functor L¯∘G′ is left adjoint to Q∘U¯.
The monoid{1} has the unique action on the set {p,*}. This trace monoid action equals L¯(G′(pt)). We have the adjoint functors between comma categories(41)
It easy to see that the category({p,*},{1})↓(FPCM∥,Set*) is isomorphic to 𝒜S♭. The composition of this isomorphism with Q∘U¯ is equal to the functor W. We obtain from this the functor L¯∘G′ left adjoint to W.


## 4. Conclusion

We have considered the category of trace monoids and basic homomorphisms and proved that this category has all colimits. This allowed us to show that the category of generalized tori is a reflective subcategory of the category of cubical sets. Then, we considered the category of trace monoid actions and proved that it is cocomplete. We built adjoint functors between the category of trace monoid actions and the category of cubical sets. We unexpectedly found that these adjoint functors translate the independence preserving morphisms in independence preserving. As a result, we have completely solved the problem of comparing the category of asynchronous systems with the category of higher dimensional automata. Earlier, the problem had been solved only for asynchronous systems satisfying the confluence condition.



---

*Source: 285071-2013-12-19.xml*