Comparing equivalences on precubical sets and spaces

E. S. Oshevskaya

Matematičeskie trudy, Tome 16 (2013) no. 1, pp. 150-188.

Résumé

We study equivalences of concurrent processes represented by objects of algebraic topology. We use methods of category theory and consider precubical sets (analogs of semisimplicial sets) and precubical spaces (analogs of cell complexes). In particular, we consider categories of these objects and construct subcategories of path-objects. We define open morphisms with respect to these subcategories and formulate criteria for a morphism to be open. We prove that the equivalence of precubical sets (spaces) based on open morphisms coincides with a behavioral equivalence of concurrent processes.

Bibliographie

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

[2] Berger M., Gostiaux B., Differential Geometry: Manifolds, Curves, and Surfaces, Springer-Verlag, New York, 1987 | MR

[3] Fajstrup L., “Dicovering spaces”, Homology Homotopy Appl., 5:2 (2003), 1–17 | MR | Zbl

[4] Fajstrup L., “Dipaths and dihomotopies in a cubical complex”, Adv. in Appl. Math., 35:2 (2005), 188–206 | DOI | MR | Zbl

[5] Fahrenberg U., “Directed Homology”, Electronic Notes Theoret. Comput. Sci., 100 (2004), 111–125 | DOI | MR

[6] Fahrenberg U., “A category of higher-dimensional automata”, Foundations of Software Science and Computation Structures, Lecture Notes in Comput. Sci., 3441, ed. V. Sassone, Springer, Berlin, 2005, 187–201 | DOI | MR | Zbl

[7] van Glabbeek R. J., “On the expressiveness of higher dimensional automata”, Theor. Comput. Sci., 356:3 (2006), 265–290 | DOI | MR | Zbl

[8] Goubault E., The Geometry of Concurrency, Ph D Thesis, Ecole Normale Superieure, Paris, 1995

[9] Goubault E., Jensen T. P., “Homology of higher-dimensional automata”, CONCUR' 92 (Stony Brook, NY, 1992), Lecture Notes in Comput. Sci., 630, ed. R. Cleaveland, Springer, Berlin, 1992, 254–268 | DOI | MR

[10] Grandis M., “Directed combinatorial homology and noncommutative tori (the breaking of symmetries in algebraic topology)”, Math. Proc. Cambridge Philos. Soc., 138:2 (2005), 233–262 | DOI | MR | Zbl

[11] Hune T., Nielsen M., “Timed bisimulation and open maps”, Mathematical Foundations of Computer Science (Brno, 1998), Lecture Notes in Comput. Sci., 1450, ed. L. Brim, Springer, Berlin, 1998, 378–387 | DOI | MR

[12] Joyal A., Nielsen M., Winskel G., “Bisimulation from open maps”, Inform. and Comput., 127:2 (1996), 164–185 | DOI | MR | Zbl

[13] Nielsen M., Cheng A., “Observing behavior categorically”, Foundations of Software Technology and Theoretical Computer Science (Bangalore, 1995), Lecture Notes in Comput. Sci., 1026, ed. P. S. Thiagarajan, Springer, Berlin, 1995, 263–278 | DOI | MR

[14] Nielsen M., Winskel G., “Petri nets and bisimulation”, Theor. Comput. Sci., 153:1–2 (1996), 211–244 | DOI | MR | Zbl

[15] Oshevskaya E. S., Virbitskaite I. B., Best E., “Unifying equivalences for higher dimensional automata”, Fundam. Inform., 119:3–4 (2012), 357–372 | Zbl

[16] Pratt V. R., “Modeling Concurrency with Geometry”, Proc. 18th Ann. ACM Symposium on Principles of Programming Languages, ACM Press, New York, 1991, 311–322

[17] Sassone V., Cattani G. L., “Higher-dimensional transition systems”, 11th Annual IEEE Symposium on Logic in Computer Science (New Brunswick, NJ, 1996), IEEE Computer Society Press, Los Alamitos, CA, 1996, 55–62 | MR

[18] Virbitskaite I. B., Gribovskaya N. S., “Open maps and observational equivalences for timed partial order models”, Fund. Inform., 60:1–4 (2004), 383–399 | MR | Zbl