Geodesic
Homology and bisimulation of asynchronous transition systems and Petri nets
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 863-877.

Voir la notice de l'article provenant de la source Math-Net.Ru

Homology groups of labelled asynchronous transition systems and Petri nets are introduced. Examples of computing the homology groups are given. It is proved that if labelled asynchronous transition systems are bisimulation equivalent, then they have isomorphic homology groups. A method of constructing a Petri net with given homology groups is presented.
Keywords: homology groups, simplicial complex, trace monoid, partial action, asynchronous system, Petri net.
Mots-clés : bisimulation 
@article{SEMR_2014_11_a42,
     author = {A. A. Husainov},
     title = {Homology and bisimulation of asynchronous transition systems and {Petri} nets},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {863--877},
     publisher = {mathdoc},
     volume = {11},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2014_11_a42/}
}
TY  - JOUR
AU  - A. A. Husainov
TI  - Homology and bisimulation of asynchronous transition systems and Petri nets
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2014
SP  - 863
EP  - 877
VL  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2014_11_a42/
LA  - en
ID  - SEMR_2014_11_a42
ER  - 
%0 Journal Article
%A A. A. Husainov
%T Homology and bisimulation of asynchronous transition systems and Petri nets
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2014
%P 863-877
%V 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2014_11_a42/
%G en
%F SEMR_2014_11_a42
A. A. Husainov. Homology and bisimulation of asynchronous transition systems and Petri nets. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 863-877. http://geodesic.mathdoc.fr/item/SEMR_2014_11_a42/

[1] A. Joyal, M. Nielsen, G. Winskel, “Bisimulation from open maps”, Information and Computation, 127 (1996), 164–185 | DOI | MR | Zbl

[2] R. Milner, Communication and concurrency, International Series in Computer Science, Prentice Hall, New York, 1989 | Zbl

[3] M. Nielsen, G. Winskel, “Petri nets and bisimulation”, Theoretical Computer Science, 153:1–2 (1996), 211–244 | DOI | MR | Zbl

[4] M. Herlihy, N. Shavit, “The Topological Structure of Asynchronous Computability”, Journal of ACM, 46:6 (1999), 858–923 | DOI | MR | Zbl

[5] E. Goubault, T. P. Jensen, “Homology of higher dimensional automata”, Lecture Notes in Computer Science, 630, Springer, Berlin, 1992, 254–268 | DOI | MR

[6] E. Goubault, The Geometry of Concurrency, Ph. D. Thesis, Ecole Normale Supérieure, 1995

[7] L. Fajstrup, M. Raußen, E. Goubault, “Algebraic topology and concurrency”, Theoretical Computer Science, 357:1–3 (2006), 241–278 | DOI | MR | Zbl

[8] E. Goubault, E. Haucourt, S. Krishnan, “Covering space theory for directed topology”, Theory and Applications of Categories, 22:9 (2009), 252–268 | MR | Zbl

[9] U. Fahrenberg, A. Legay, “History-Preserving Bisimilarity for Higher-Dimensional Automata via Open Maps”, Electronic Notes in Theoretical Computer Science, 538 (2013), 165–178 | DOI | MR

[10] A. Husainov, “On the homology of small categories and asynchronous transition systems”, Homology, Homotopy and Applications, 6:1 (2004), 439–471 | DOI | MR | Zbl

[11] A. A. Khusainov, V. E. Lopatkin, I. A. Treshchev, “Studying a mathematical model of parallel computation by algebraic topology methods”, Journal of Applied and Industrial Mathematics, 3:3 (2009), 353–363 | DOI | MR

[12] A. A. Husainov, “The cubical homology of trace monoids”, Far Eastern Mathematical Journal, 12:1 (2012), 108–122 http://mi.mathnet.ru/eng/dvmg/v12/i1/p108 | MR | Zbl

[13] A. A. Husainov, “The Homology of Partial Monoid Actions and Petri Nets”, Applied Categorical Structures, 21:6 (2013), 587–615 | DOI | MR | Zbl

[14] G. Winskel, M. Nielsen, “Models for Concurrency”, Handbook of Logic in Computer Science, v. 4, eds. Abramsky, Gabbay Maibaum, Oxford University Press, Oxford, 1995, 1–148 | MR

[15] M. A. Bednarczyk, Categories of Asynchronous Systems, Ph. D. thesis, University of Sussex; Report No 1/88, 1988

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

[17] E. H. Spanier, Algebraic topology, McGraw-Hill Book Company, New York, 1966 | MR | Zbl