The Cubical Homology of Trace Monoids Husainov A.A. /en/files/CHTM2011

2 The purpose of the presentation To describe the solution of the problem posed by the author inTo describe the solution of the problem posed by the author in Husainov A., ``On the homology of small categories and asynchronous transition systems``, Homology Homotopy Appl. 2004, 1 (6), (Open Problem 1) To develop the homology theory for sets with partial trace monoid actions.To develop the homology theory for sets with partial trace monoid actions.

3 Problems Investigation of a relationship between the cubical homology groups of generalized tori and homology groups of sets with partial trace monoid actions.Investigation of a relationship between the cubical homology groups of generalized tori and homology groups of sets with partial trace monoid actions. Development of algorithms for computing the homology groups of asynchronous systems, Petri nets, and Mazurkiewicz trace languagesDevelopment of algorithms for computing the homology groups of asynchronous systems, Petri nets, and Mazurkiewicz trace languages

4 Trace monoids Let E be a set, I E E an irreflexive and symmetric relation (of independence). (a,b) I ab=ba & ab A trace monoid (or free partially commutative monoid) M(E,I) is the factor monoid E * /( ) of the monoid E * of words in alphabet E by a least equivalence relation for which uabv ubav, for all (a,b) I, u E *, v E *

5 Examples of trace monoid E ={a,b}, I ={(a,b),(b,a)}, M(E,I) N 2 is the free commutative monoid M(E,I) N 2 is the free commutative monoid E ={a,b}, I =, M(E,I) {a,b} * is the free monoid M(E,I) {a,b} * is the free monoid E ={a,b,c}, I = {(a,b),(b,a), (b,c),(c,b)}, M(E,I) {a,b,c} * /(ab ) consists of the traces M(E,I) {a,b,c} * /(ab ba, bc cb) consists of the traces {1, [a], [b], [c], [aa], [ab], [ac], [bb], [bc], [ca], [cc], [aaa], …} aa ab ac ba bb bc ca cb cc

6 An interpretation of traces The trace w M(E,I) is a sequnce of actions a 1 a 2 … a n By permutations of independent elements we can bring it to the Foata normal form (b 1 b 2 …b p )(b p+1 … b q )… (b r+1 … b n ) (The brackets contain the actions to be performed at the same time) (The brackets contain the actions to be performed at the same time)

7 State space Assign to a E some partial mappings S S. A state space (M(E,I), S) consists of a set S (of states) with a partial right action of M(E,I). For example, E={a,b}, I={(a,b), (b,a)}

8 State space with an augmentation By adding the state of ``freezing * we get The traces are interpreted as computational processes. For example, the trace aaba includes actions in the state *

9 The category of states Augmented state category K (S): Objects S { }. Morphisms are triples (s, w, s), s·w=s, for s,s S { }, w M(E,I) A state category K(S) K (S) is a full subcategory with objects S

10 The homology group of a category Let С be a small category, F: С Ab a functor Groups H n (C,F) = Ker d n / Im d n+1 are called homology groups of C with corfficients in F

11 Computing the homology groups Let k be a field and be a complex of vector spaces Then the n th homology vector space equals H n =Ker d n / Im d n+1 = k dimC n -r(d n )-r(d n+1 ), where r(A) denotes the rank of a matrix A Proposition. Let A be a matrix with integer entries. Then there are matrixes S, T, D such that 1)A= T D S2) |det S|=|det T|=1 3) D is a diagonal matrix where 1 | 2 | … | r Proposition. If instead of k is considered Z, then the homology groups are computed 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 )

12 Computing the integral homology groups of a poset 1 Here F= Z. The complex consists of the free Abelian groups

13 Computing the integral homology groups of a poset 2

14 Computing the integral homology groups of a poset 3 The entries of the normal forms are equal to 1, therefore

15 Homology of small categories as derived functors of the colimit Proposition. Let colim C : Ab C Ab be the colimit functor, F: C Ab an object of Ab C, 0 F P 0 P 1 … P n P n+1 … a projective rezolution, С the complex 0 colim C P 0 colim C P 1 … … colim C P n colim C P n+1 … Then H n (C,F) H n (С ).

16 Two problems K(S),Z In the author paper in 2004, it was developed an algorithm for computing the group H 1 (K(S),Z) and formulated Problem 1. Construct an algorithm for computing integral homology of CE nets If we find an algorithm to compute Hn (K (S), Z) for the categories of states, then this problem will be solved. K (S),F It was proved that if M(E,I) does not contain triples of pairwise independent generators, then H n (K (S),F)=0 for n>2. K (S),F Problem 2. Let n>0 be the maximal number of pairwise independent generators. Prove that H k (K (S),F)=0 for k>n. In the case of finite E this conjecture proved by L.Yu. Polyakova (Siberian J. Math. 48:6, 2007). In general solved by the author (Sb.: Math. 199:12, 2008).

17 Semicubical sets

18 Geometric realization Geometric realization |X| of semicubical set is the topological spaceon the smallest equivalence relation ( ) for which Example.

19 The semicubical set of a state space Let S * = S { * }. Assign to a state space (M(E,I),S) the semicubical set Q n (E,I,S)= {(x,a 1,…, a n )| x S *, a i <a j & (a i,a j ) I, for all 1 i < j n}

20 Topological space of intermediate states Introduce ``intermediate states as points of topological space obtained from * * by gluing stars, segments connecting them, and the unit squares. We will get the geometric realization |Q(E,I,S)| of the semicubical set aa * s2s2 s3s3 a * a a * s0s0 s1s1 s4s4 * bb b bb bb a aa * b a

21 Generalized tori A generalized torus is the semicubical set T n (E,I)={(a 1,…, a n )| a i <a j & (a i,a j ) I, for all 1 i < j n} Geometric realization |T(E,I)| for I=(E E)\{(a,a)| a E} is homeomorphic to the usual torus T n. In the freezing state, the intermediate states runs the points of the generalized torus. Therefore, generalized tori constitute an obstacle to solving Problem 1. 1{a,b} {ab}… T({a,b},{(a,b),(b,a)})

22 Examples of generalized tori Independence graphGeometric realization |T(E,I)| ba a b c Torus T 2 The rotation surface of the figure 8 a bBouquet of circles ac b T 2 T 1

23 Homological systems Let X be a semicubical set. A homological system on X is a family of abelian groups F(x), and for which the following diagram is commutative

24 Homology groups of semicubical sets Definition. H n (X,F) is the homology groups of a complex Example. H 1 (X,Z[ ])=Z, H n (X,Z[ ])=0 for all n 1.

25 A factorization category Let C be a small category. Objects of a factorization category Fact(C) are morphisms in C, and morphisms defined by commutative diagrams Example. Consider a trace monoid M(E,I) as a category with an unique object. Then objects in Fact(M(E,I)) are traces. Morphisms are given by pairs of traces (f,g) for which g f=

26 Leech homology of trace monoids as the homology of generalized tori Definition. Leech homology groups of a monoid M with coefficients in a functor F: Fact(M) op Ab are the groups H n ((Fact(M)) op,F), n 0. Theorem. Let F: Fact(M(E,I)) op Ab be a functor. Then there exists a homological system F on T(E,I) such that H n (Fact(M(E,I)) op,F) H n (T(E,I), F)

27 Global dimension of a trace monoid Theorem. For any functors F: Fact(M(E,I)) Ab, n 0, it is true H n (Fact(M(E,I)),F) H n (T(E,I), F) Corollary. Let A be an abelian category with copruducts, n is a maximal cardinality of pairwise commuting elements E. Then in each of the following cases: 1)A has exact coproducts (i.e. A satisfy to AB4) 2)A has enough projectives Conjecture. This inequality is true for all abelian categories with coproducts (AB3)

28 Global dimension of a polynomial ring in partially commuting variables Example Example. Let k be a field, and x 1, x 2, x 3, x 4, x 5 be variables. Let the commuting symbols connected by edges in the graph Then gl.dim k x 1,x 2,x 3,x 4,x 5 /(I) =2, where (I) =({x i x j -x j x i | (x i,x j ) I}).

29 Homology of augmented state category. Theorem. H n (K * (T,F)) is isomorphic to homology Corollary. If the cardinality of pairwise independent events n, then H k (K * (T,F))=0, k>n. (The solution of Problem 2)

30 Example of computing the homology groups |S |=|{s 0, s 1, }|=3 |S E|=|{(s 0,a), (s 0,b), (s 1,a), (s 1,b), (,a), (,b)}|=6 | S T 2 (E,I) |=|{(s 0,a,b), (s 1,a, b), (,a,b)}|

31 Mazurkiewicz trace languages For v, w M(E,I), we write v w, if ( u M(E,I)) vu = w. Let P(E,I)=(M(E,I), ) be a poset of all traces. Definition Definition. L M(E,I) is prefix closed, if v < w L v L. Let (M(E,I), L { }) be a trace monoid with the action v w=vw, if vw L, and v w=, otherwise.

32 Homology groups of a trace language Theorem Theorem. H n (K (L), Z) H n (P(E,I),Z[L]) Z p n Here p n is the cardinality of set of n-cliques in the independence graph p 1 =5, p 2 = 4, p 3 =1

33 The poset of traces and its homology groups Theorem. H n (P(E,I),Z[L]) n-1 (M(E,I)\L), for n 1. Corollary. H 1 (K (L), Z) is free abelian group. Conjecture. H 1 (K (S), Z) is free for every set with partial action of a trace monoid. The homological properties of the trace poset 1) If I consists of all (a,b), for which a b, then H n (P(E,I),Z[L])=0 for all n>0. 2) If I=, then H n (P(E,I),Z[L])=0 for all n>0. 3) For arbitrary finite generated abelian groups A 1, …, A k, with free A 1, there exists M(E,I) such that H n (P(E,I),Z[{1}]) A n for all 1 n k

34 Baues-Wirsching homology Let X be a right M(E,I)-set, K(X) a category with objects x X and morphisms F: Fact(K(X)) op Ab a functor, U: K(X) M(E,I) a functor forgetting the beginnings and ends of morphisms Theorem Theorem. H n (Fact(K(X)) op,F) H n (Fact(M(E,I)) op,L(F)) Here L(F) is a left Kan extension of a functor F along a functor Fact(K(X)) op Fact(M(E,I)) op, defined by the functor U.

35 Solution of Problem 1 Corollary Corollary. Let (M(E,I),S) be a state space, K(S) a category of states. Groups H n (K(S), Z) are isomorphic to the homology groups of the complex

36 Algorithm for computing the homology groups of the state categories For example C 0 =Z{s 0,s 1 }, C 1 =Z{(s 0,a), (s 0,b), (s 1,a)}, C 2 =Z{(s 0,a,b)} We got H 0 =Z 2-1 =Z, H 1 =Z = Z

37 Elementary Petri nets Elementary Petri nets CE net consists of action blocks and conditions which indicate the state of data availability. t1t1 t2t2 p1p1 p2p2 t1t1 t1t1 t2t2 p1p1 p2p2 t1t1 t2t2 p1p1 p2p2 t2t2 t3t3 t3t3 t3t3 p3p3 p4p4 p5p5 p3p3 p3p3 p4p4 p5p5 p4p4 p5p5

38 Homology groups of CE nets Let E={t 1, …, t n }. I={(t i,t j )| not having common data } In example, I={(t 1,t 3 ), (t 3,t 1 )} S={{p 1, p 2 },{p 4 },{p 1, p 5 }} The action: {p 1, p 2 } t 1 ={p 4 } {p 1, p 2 } t 2 ={p 1, p 5 } Definition Definition. Homology groups of CE net are defined as H n (K(S), Z). t1t1 t2t2 p1p1 p2p2 t3t3 p3p3 p4p4 p5p5

39 Computing the homology groups of CE nets For the pipeline We got H 0 =Z 8-7 =Z, H 1 =Z = Z t1t1 t2t2 t3t3 t4t4 (0,1,1)(0,1,0) (1,1,1) (0,0,0)(0,0,1) (1,0,1)(1,0,0) (1,1,0) t1t1 t1t1 t1t1 t1t1 t4t4 t4t4 t4t4 t4t4 t2t2 t2t2 t3t3 t3t3

40 Perspectives Introduction of Goubault homology groups as homology groups of the state category Investigation of the relationship of and homological and bisimilar invariants The studying the homotopy colimit of diagrams over the state categories