Simplicial models of trace spaces

Raussen, Martin¹

¹Department of Mathematical Sciences, Aalborg University, Fredrik Bajersvej 7G, DK-9220 Aalborg Øst, Denmark

Algebraic and Geometric Topology, Tome 10 (2010) no. 3, pp. 1683-1714

Résumé

Directed algebraic topology studies topological spaces in which certain directed paths (d-paths) are singled out; in most cases of interest, the reverse path of a d-path is no longer a d-path. We are mainly concerned with spaces of directed paths between given end points, and how those vary under variation of the end points. The original motivation stems from certain models for concurrent computation. So far, homotopy types of spaces of d-paths and their topological invariants have only been determined in cases that were elementary to overlook.

In this paper, we develop a systematic approach describing spaces of directed paths – up to homotopy equivalence – as finite prodsimplicial complexes, ie with products of simplices as building blocks. This method makes use of a certain poset category of binary matrices related to a given model space. It applies to a class of directed spaces that arise from a certain class of models of computation – still restricted but with a fair amount of generality. In the final section, we outline a generalization to model spaces known as Higher Dimensional Automata.

In particular, we describe algorithms that allow us to determine not only the fundamental category of such a model space, but all homological invariants of spaces of directed paths within it. The prodsimplical complexes and their associated chain complexes are finite, but they will, in general, have a huge number of cells and generators.

Détail

DOI : 10.2140/agt.2010.10.1683

Keywords: d-path, d-space, prodsimplicial complex, poset category, homotopy equivalence

Bibliographie

[1] R Brown, P J Higgins, Colimit theorems for relative homotopy groups, J. Pure Appl. Algebra 22 (1981) 11

[2] R Brown, P J Higgins, On the algebra of cubes, J. Pure Appl. Algebra 21 (1981) 233

[3] E W Dijkstra, Co-operating sequential processes, from: "Programming Languages" (editor F Genuys), Academic Press (1968) 43

[4] U Fahrenberg, M Raussen, Reparametrizations of continuous paths, J. Homotopy Relat. Struct. 2 (2007) 93

[5] L Fajstrup, E Goubault, M Raussen, Detecting deadlocks in concurrent systems, from: "CONCUR’98 : concurrency theory (Nice)" (editors D Sangiorgi, R de Simone), Lecture Notes in Comput. Sci. 1466, Springer (1998) 332

[6] L Fajstrup, M Raussen, E Goubault, Algebraic topology and concurrency, Theoret. Comput. Sci. 357 (2006) 241

[7] L Fajstrup, M Raussen, E Goubault, E Haucourt, Components of the fundamental category. Homotopy theory, Appl. Categ. Structures 12 (2004) 81

[8] L Fajstrup, S Sokolowski, Infinitely running concurrents processes with loops from a geometric viewpoint, Elec. Notes Theor. Comput. Sci. 39 (2000)

[9] R J Van Glabbeek, On the expressiveness of higher dimensional automata, Theoret. Comput. Sci. 356 (2006) 265

[10] E Goubault, E Haucourt, Components of the fundamental category. II, Appl. Categ. Structures 15 (2007) 387

[11] M Grandis, Directed homotopy theory. II. Homotopy constructs, Theory Appl. Categ. 10 (2002) 369

[12] M Grandis, Directed homotopy theory. I, Cah. Topol. Géom. Différ. Catég. 44 (2003) 281

[13] M Grandis, Directed algebraic topology. Models of non-reversible worlds, 13, Cambridge Univ. Press (2009)

[14] J Gunawardena, Homotopy and concurrency, Bull. EATCS 54 (1994) 184

[15] M Herlihy, S Rajsbaum, Algebraic topology and distributed computing—a primer, from: "Computer science today" (editor J van Leeuwen), Lecture Notes in Comput. Sci. 1000, Springer (1995) 203

[16] J F Jardine, Path categories and resolutions, Preprint (2009)

[17] T Kaczynski, K Mischaikow, M Mrozek, Computational homology, 157, Springer (2004)

[18] T Kaczynski, M Mrozek, M Ślusarek, Homology computation by reduction of chain complexes, Comput. Math. Appl. 35 (1998) 59

[19] L Khachiyan, E Boros, K Elbassioni, V Gurvich, A new algorithm for the hypergraph transversal problem, from: "Computing and combinatorics" (editor L Wang), Lecture Notes in Comput. Sci. 3595, Springer (2005) 767

[20] D Kozlov, Combinatorial algebraic topology, 21, Springer (2008)

[21] J Matoušek, G M Ziegler, Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Deutsch. Math.-Verein. 106 (2004) 71

[22] J Milnor, On spaces having the homotopy type of a CW–complex, Trans. Amer. Math. Soc. 90 (1959) 272

[23] V Pratt, Modeling concurrency with geometry, from: "POPL ’91 : Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages", ACM (1991) 311

[24] M Raussen, On the classification of dipaths in geometric models for concurrency. Geometry and concurrency, Math. Structures Comput. Sci. 10 (2000) 427

[25] M Raussen, Deadlocks and dihomotopy in mutual exclusion models, Theoret. Comput. Sci. 365 (2006) 247

[26] M Raussen, Invariants of directed spaces, Appl. Categ. Structures 15 (2007) 355

[27] M Raussen, Reparametrizations with given stop data, J. Homotopy Relat. Struct. 4 (2009) 1

[28] M Raussen, Trace spaces in a pre-cubical complex, Topology Appl. 156 (2009) 1718

[29] M Raussen, Simplicial models for trace spaces, Tech. Report R-2010-02, Dept. of Math. Sciences, Aalborg University (2010)

[30] G Winskel, M Nielsen, Models for concurrency, from: "Handbook of logic in computer science, Vol. 4" (editors S Abramsky, D M Gabbay, T S E Maibaum), Handb. Log. Comput. Sci. 4, Oxford Univ. Press (1995) 1