Homology groups of asynchronous systems, Petri nets, and trace languages

A. A. Khusainov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 13-44.

Résumé

The paper is devoted to the homology groups of mathematical models for concurrent systems. It is proved that the homology groups of a set with a trace monoid action is isomorphic to the homology groups of a corresponding semi-cubical set. Homology groups of Petri nets and Mazurkiewicz trace languages are introduced. It is shown that in dimensions $n\geqslant2$, the homology groups of Petri nets and Mazurkiewicz languages can be arbitrary, up to direct summands which are equal to the homology groups of generalized tori. Examples of the computing the homology groups of state spaces and Petri nets are considered. The integral homology groups of some partially ordered sets of traces are investigated.

Détail

Keywords: semi-cubical set, homology of small categories, free partially commutative monoid, trace monoid, Petri nets, trace languages.
Mots-clés : asynchronous transition system

Bibliographie

[1] M. W. Shields, “Concurrent machines”, The Computer Journal, 28 (1985), 449–465 | DOI | MR | Zbl

[2] M. A. Bednarczyk, Categories of Asynchronous Systems, Ph.D. Thesis, University of Sussex, 1988; $marek} http://www.ipipan.gda.pl/<nobr>$ \widetilde{

[3] M. Nielsen, G. Rozenberg, P. S. Thiagarajan, “Behavioural notions for elementary net systems”, Distributed Computing, 4:1 (1990), 45–57 | DOI | MR

[4] R.J. van Glabbeek, “On the Expressiveness of higher dimensional automata”, Theoretical Computer Sci., 356:3 (2006), 265–290 | DOI | MR | Zbl

[5] E. Goubault, S. Mimram, Formal Relationships Between Geometrical and Classical Models for Concurrency, Preprint, Cornell Univ., New York, 2010, 20 pp.; arXiv: 1004.2818

[6] A. A. Khusainov, V.V. Tkachenko, “Gruppy gomologii asinkhronnykh sistem perekhodov”, Matematicheskoe modelirovanie i smezhnye voprosy matematiki, Sb. nauch. trudov, izd-vo KhGPU, Khabarovsk, 2003, 23–33

[7] 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 | MR | Zbl

[8] E. Goubault, The Geometry of Concurrency, Ph.D. Thesis, Ecole Normale Supérieure, 1995; $goubault} http://www.dmi.ens.fr/<nobr>$ \widetilde{

[9] P. Gaucher, “About the globular homology of higher dimensional automata”, Cah. Topol. Geom. Differ., 43:2 (2002), 107–156 | MR | Zbl

[10] A. A. Khusainov, V. E. Lopatkin, I. A. Treschev, “Issledovanie matematicheskoi modeli parallelnykh vychislitelnykh protsessov metodami algebraicheskoi topologii”, Sib. zhurn. industr. matem., 11:1 (2008), 141–151 | MR

[11] L. Yu. Polyakova, “Rezolventy dlya svobodnykh chastichno kommutativnykh monoidov”, Sib. mat. zhurn., 48:6 (2007), 1295–1304 | MR | Zbl

[12] A. Mazurkiewicz, “Trace theory”, Advances in Petri Nets 1986, Lecture Notes in Computer Science, 255, Springer-Verlag, Berlin, 1987, 278–324 | MR

[13] A. A. Khusainov, “O gruppakh gomologii polukubicheskikh mnozhestv”, Sib. mat. zhurn., 49:1 (2008), 224–237 | MR | Zbl

[14] T. Kaczynski, K. Mischaikov, M. Mrozek, “Computational homology”, Homology Homotopy Appl., 5:2 (2003), 233–256 | MR | Zbl

[15] T. Kaczynski, K. Mischaikov, M. Mrozek, Computational homology, Appl. Math. Sci., 157, Springer-Verlag, New York, 2004 | MR | Zbl

[16] U. Fahrenberg, “A Category of Higher-Dimensional Automata”, Foundations of software science and computational structures, Lecture Notes in Computer Science, 3441, Springer-Verlag, Berlin, 2005, 187–201 | DOI | MR | Zbl

[17] P. Gabriel, M. Tsisman, Kategorii chastnykh i teoriya gomotopii, Mir, Moskva, 1971 | MR | Zbl

[18] D. Quillen, “Higher Algebraic K-Theory: I”, Higher K-Theories, Lecture Notes in Math., 341, Springer-Verlag, Berlin, 1973, 85–147 | DOI | MR

[19] S. Maklein, Kategorii dlya rabotayuschego matematika, FIZMATLIT, Moskva, 2004

[20] U. Oberst, “Homology of categories and exactness of direct limits”, Math. Z., 107 (1968), 87–115 | DOI | MR | Zbl

[21] A. A. Husainov, “On the Leech dimension of a free partially commutative monoid”, Tbilisi Math. J., 1:1 (2008), 71–87 ; http://ncst.org.ge/Journals/TMJ/index.html | MR | Zbl

[22] A. A. Khusainov, “Kubicheskie gomologii i razmernost Licha svobodnykh chastichno kommutativnykh monoidov”, Matem. sb., 199:12 (2008), 129–154 | MR | Zbl

[23] V. Diekert, Y. Métivier, “Partial Commutation and Traces”, Handbook of formal languages, 3, Springer-Verlag, New York, 1997, 457–533 | DOI | MR

[24] V. Lopatkin, The Torsion of Homology Groups of M(E,I)-sets, Preprint, Cornell Univ., New York, 2008, 5 pp. ; arXiv: 0811.3722 | Zbl

[25] V.E. Lopatkin, Issledovanie matematicheskikh modelei parallelnykh vychislitelnykh sistem metodami algebraicheskoi topologii, Dissertatsiya na soisk. uch. stepeni kand. fiz.-mat. nauk., Komsomolskii-na-Amure gos. tekhn. universitet, Komsomolsk-na-Amure, 2010

[26] E. Spener, Algebraicheskaya topologiya, Mir, Moskva, 1971 | MR

[27] Dzh. Piterson, Teoriya setei Petri i modelirovanie sistem, Mir, Moskva, 1984

[28] G. Winskel, “Petri nets, algebras, morphisms and compositionality”, Information Computation, 72:3 (1987), 197–238 | DOI | MR | Zbl