The homology groups of a partial monoid action category Ahmet A. Husainov

2 Partial monoid action on a set Denote by PSet the category of sets and partial maps Let M be a monoid and let S be a set. Partial right action of M on S is a homomorphism of monoids M op PSet(S,S) Example 1. M=N 2 ={a p b q : p, q=0, 1, 2, …}, S= {s 0, s 1, s 2, s 3, s 4 } s 0 a=s 1, s 0 b=s 2 s 1 a=s 4, s 1 b=s 3 s 2 a=s 3

3 A category for a monoid partial action The category K(S) of partial actions has objects s S. Morphisms s 1 s 2 are triples (s 1,, s 2 ). Composition is defined by (s 2, 2, s 3 ) (s 1, 1, s 2 )= (s 1, 1 2, s 3 ). In Example 1, K(S) is a partially ordered set with s 0 <s 1, s 0 <s 2 s 1 <s 3, s 1 <s 4 s 2 <s 3

4 Trace monoids Let E be a set and let I E E be an irrefexive symmetric relation (of independence) Free partially commutative monoid (or trace monoid) M(E,I) is a quotient monoid E * /( ) where E * is a monoid of all words in alphabet E and ( ) is smallest equivalence relation for which uabv ubav, for all (a,b) I, u E *, v E * Trace monoid M(E,I) is called to be locally finite dimensional if E does not contain infinite subsets of pairwise independent elements

5 Examples of trace monoids E ={a,b}, I ={(a,b),(b,a)}, M(E,I) N 2 is a free commutative monoid E ={a,b}, I =, M(E,I) {a,b} * is a free monoid

6 Interpretation of traces Any trace w M(E,I) can be interpreted as a finite sequence of actions a 1 a 2 … a n Transposing neighboring pairs of independent elements, it can be reduced to Foata normal form [ b 1 b 2 …b p ] [ b p+1 … b q ]… [ b r+1 … b n ] (actions bounded square brackets are performed concurrently)

7 Classifying space Let C be a small category. Its classifying space BC can be constructed by gluing cells. We assign to each object c ObC the point. Assign to each morphism c 0 с 1 the segment, to each pair c 0 с 1 с 2 the triangle and etc.

8 Purpose of the report The studying Baues-Wirsching homology groups of the category K(S) for a monoid partial action on a set S. Application of the Baues-Wirsching homology for building the algorithms for computing the homology groups of the space B(K (S)) and directed homology groups for a partial trace monoid action.

9 Homology of categories Let C be a small category and let colim C : Ab C Ab be the colimit fuctor. For any functor F: C Ab considered as an object in Ab C, there exists a projective resolution 0 F P 0 P 1 … P n P n+1 … and a complex С of Abelian groups 0 colim C P 0 colim C P 1 … … colim C P n colim C P n+1 … The groups H n (C,F) H n (С ), n 0, are called homology groups of the category C with coefficients in F.

10 Category of factorizations Let C be a small category. Objects of a factorization category Fact(C) are all morphisms of C. Morphisms in Fact(C) are given by commutative diagrams Example 2. Let M be a monoid considered as the category. Then Ob(Fact (M) )= M. Its morphisms from to are pairs (f,g) of f, g M for which g f=. Proposition 1. Fact(C) Fact(C op )

11 Baues-Wirsching homology Let C be a small category. For any functor F: Fact(C) op Ab, H n (Fact(C) op,F) are called Baues-Wirsching homology groups of C with coefficients in contravariant natural systems F on C. If C=M is a monoid, then H n (Fact(M) op,F) are Leech homology groups of a diagram F

12 Baues-Wirsching homology Let S be a set with partial action of a monoid M. Let K(S) be the action category with morphisms Consider a functor F: Fact(K(S)) op Ab and the functor U: K(S) M op defined as U(s 1,,s 2 )=. Theorem. H n (Fact(K(S)) op,F) H n (Fact(M) op,L(F)) Here L(F) is a left Kan extension of the functor F along the functor Fact(K(S)) op Fact(M) op, determined by the functor U.

13 Homology of classifying space for the action category Let M(E,I) be a trace monoid. For n= 0, 1, 2, …, introduce sets T n (E,I)={(a 1,…, a n )| a i <a j & (a i,a j ) I, for all 1 i < j n} In particular, T 0 (E,I)={1}. For an arbitrary set S, denote by LS a free Abelian group generated by S.

14 Homology of the classifying space for the action category A polygon S over M(E,I) is a set with a partial action of a trace monoid. Corollary 1. Let S be a polygon over a locally finite dimensional trace monoid M(E,I). Groups H n (B(K(S))) isomorphic to homology groups of complex Here s S denotes that s is defined.

15 Computing the homology groups Let k be a field and let be a complex of vector spaces. Then H n =Ker d n / Im d n+1 = k dimC n -r(d n )-r(d n+1 ) where r(A) is denoted the rank of matrix A Proposition 2. Let A be a matrix with integer entries. Then there are matrixes S, T, D, for which 1)A= T D S2) |det S|=|det T|=1 3) D is a diagonal matrix with 1 | 2 | … | r D is Smith normal form of A If k=Z is a ring of integers, then the homology groups can be computing by the Smith normal form: H n =Ker d n / Im d n+1 = Z dimC n -r(d n )-r(d n+1 ) Z/ 1 Z … Z/ r Z, r=r(d n+1 )

16 Example for Corollary 1 Example 3. C 0 =L{s 0,s 1 }, C 1 =L{(s 0,a), (s 0,b), (s 1,a)}, C 2 =L{(s 0,a,b)} We obtain H 0 =Z 2-1 =Z, H 1 =Z = Z

17 Directed homology groups Let 0 Z: K(S) Ab and 1 Z: K(S) op Ab be functors with values Z (group of integers) on objects s and defined at morphisms as Groups H n 0 (S,M(E,I)) = def H n (K(S), 0 Z) and H n 1 (S,M(E,I)) = опр H n (K(S) op, 1 Z) are called directed homology groups.

18 Directed homology groups Corollary 2. In the conditions of Corollary 1 the groups H n 0 (S,M(E,I)) are isomorphic to homology groups of the complex consisting of the same Abelian groups but has the following differentials H n 1 (S,M(E,I)) can be computed by a similar complex with differentials

19 Example of computing the directed homology groups Example 4. Groups H 0 0 and H 1 0 C 0 =L{s 0,s 1,s 2 }, C 1 =L{(s 0,a), (s 0,b)}, We obtain H 0 0 =Z 3-1 =Z 2, H 1 0 =Z 2-1 = Z.

20 Example of computing the directed homology groups Groups H 0 1 and H 1 1 C 0 =L{s 0,s 1,s 2 }, C 1 =L{(s 0,a), (s 0,b)}, Obtain H 0 0 =Z 3-2 =Z, H 1 0 =Z 2-2 = 0.

21 Interpretation of homology groups H 0 0 and H 0 1 An element s S is initial if the action category does not has morphisms with codomain s. It is final if there are not morphisms with domain s. Groups H 0 0 (S,M(E,I)) and H 0 1 (S,M(E,I)) are free. Initial elements generated H 0 1 (S,M(E,I)), final elements generated H 0 0 (S,M(E,I)) In Figure: rk H 0 1 (S,M(E,I))=1 rk H 0 0 (S,M(E,I))=2

22 Local homology Consider decompositions and where is a functor defined as Similarly defined the functor. We obtain decomposition the directed homology groups. Local homology groups of the category for the partial trace monoid action M(E,I) on S are defined as

23 Computing the local homology groups where Differentials are defined as Proposition 3. Let S be a polygon over M(E,I). For s S, the groups can be computed by the following complex

24 Computing the local homology groups H n 0 Corollary 3. Let S be a polygon over M(E,I). For s S, we consider a simplicial scheme (s) with the set of vertexes 0 (S,E,I.s)= {a 0 E | sa 0 S}. Its sets of n-simplexes equal Recall that

25 Example 5. number of the final elements = 2 Example of computing the groups H n 0

26 Computing the local homology groups H n 1 where Differentials are defined as Proposition 4. Let S be a polygon over M(E,I). For s S, the groups can be computed by the following complex

27 Computing the local groups H n 1 number of initial elements = 1 Example 6.

28 Connection with bisimulation equivalence Corollary 4. For s S, consider the complex Let S be a polygon over M(E,I). For s S, we can remove the condition e 1 <…<e n in the complex for the computing the homology of simplicial scheme (s). There are isomorphisms

29 Connection with bisimulation equivalence Proposition 5. A morphism of polygons with labels is open if and only if the corresponding morphism of asynchronous systems is Pom -open. Let S be a polygon over M(E,I). Label function : E is a map such that ( a 1, a 2 ) I ( a 1 ) ( a 2 ). Let A=(S,M(E,I),s 0,, ) be a polygon over M(E,I) with a label function. An element s S is reachable if ( M(E,I)) s= s 0. Let S(s 0 ) the set of reachable s. Definition. A morphism of polygons with label functions A A is open, if it is given by a pair of (total) maps : S S, : E E, satisfying the following conditions 1) (s 0 )= s 0, 2) save labels, i.e. =. 3)(e 1,e 2 ) I ( (e 1 ), (e 2 ) I 4)if s is reachable, then : {s | se S} {e | (s)e S} surjective 5)if s is reachable, then : {(e 1,e 2 ) I | se 1 e 2 S} {(e 1,e 2 ) I | (s)e 1 e 2 S} is surjective

30 Connection with bisimulation equivalence Theorem. If pointed polygons A and A with label functions : E and : E are bisimulation equivalent, then s S(s 0 ) s S(s 0 ) and s S(s 0 ) s S(s 0 ) for which Pointed polygons A 1 and A 2 with labels in are bisimulation equivalent if there is a pointed polygon A and open morphisms A 1 A A 2. Consider the following complex L : Label function gives the chain morphism

31 Example of trace equivalent asynchronous systems which are not bisimulation equivalent ={ a, b, c} E={ a 1, a 2,b, c}, E={ a,b, c} ( a 1 )= ( a 2 )= a ( a )= a (b)=b (b)=b (c)=c (c)=c Trace ab and ac. Complexes

32 Perspectives Studying the homotopical colimits of diagrams on the categories of partial actions Applications of the homology groups for the studying the topology of state spaces of concurrent systems