×
Raussen, Martin

Simplicial models of trace spaces. (English) Zbl 1198.55004

Algebr. Geom. Topol. 10, No. 3, 1683-1714 (2010).
Directed algebraic topology is a field of research between concurrency and algebraic topology involving the use of a space of states equipped with an additional structure modeling time. In this kind of model, there is always an underlying state space equipped with a set of privileged continuous paths playing the role of execution paths. In general, the reverse of an execution path is not an execution path. Calculating the homotopy type of the space of execution paths is the main problem in this theory.
For example, calculating the fundamental category means calculating the path-connected components of this space [M. Grandis, Directed algebraic topology. Models of non-reversible worlds. New Mathematical Monographs 13. Cambridge: Cambridge University Press. (2009; Zbl 1176.55001)]. In other approaches like the reviewer’s approach of directed algebraic topology [P. Gaucher, Homology Homotopy Appl. 5, No. 1, 549–599, electronic only (2003; Zbl 1069.55008), Theory Appl. Categ. 22, 588–621 (2009; Zbl 1191.55013)], the homotopy type of the space of execution paths also plays a fundamental role, e.g. in the definition of the weak equivalences of model category structures. In this paper, the author develops a systematic approach describing spaces of execution paths up to homotopy equivalence as finite prodsimplicial complexes [D. Kozlov, Combinatorial algebraic topology. Algorithms and Computation in Mathematics 21. Berlin: Springer. (2008; Zbl 1130.55001)]. This approach makes feasible (at least for some class of models of computation) the calculations of some of their algebraic topological invariants. The author describes algorithms to determine not only the fundamental category of such a model space, but all homological invariants of spaces of execution paths within it.
Reviewer: Philippe Gaucher (Paris)

Cited in 2 Reviews
Cited in 16 Documents

MSC:

55P10 Homotopy equivalences in algebraic topology
55P15 Classification of homotopy type
55U10 Simplicial sets and complexes in algebraic topology
68Q55 Semantics in the theory of computing
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Keywords:

d-path; d-space; prodsimplicial complex; poset category; homotopy equivalence

Citations:

Zbl 1176.55001; Zbl 1069.55008; Zbl 1191.55013; Zbl 1130.55001
PDF BibTeX XML Cite
\textit{M. Raussen}, Algebr. Geom. Topol. 10, No. 3, 1683--1714 (2010; Zbl 1198.55004)
Full Text: DOI

References:

[1] R Brown, P J Higgins, Colimit theorems for relative homotopy groups, J. Pure Appl. Algebra 22 (1981) 11 · Zbl 0475.55009
[2] R Brown, P J Higgins, On the algebra of cubes, J. Pure Appl. Algebra 21 (1981) 233 · Zbl 0468.55007
[3] E W Dijkstra, Co-operating sequential processes (editor F Genuys), Academic Press (1968) 43
[4] U Fahrenberg, M Raussen, Reparametrizations of continuous paths, J. Homotopy Relat. Struct. 2 (2007) 93 · Zbl 1186.55004
[5] L Fajstrup, E Goubault, M Raussen, Detecting deadlocks in concurrent systems (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 · Zbl 1099.55003
[7] L Fajstrup, M Raussen, E Goubault, E Haucourt, Components of the fundamental category. Homotopy theory, Appl. Categ. Structures 12 (2004) 81 · Zbl 1078.55020
[8] L Fajstrup, S Sokolowski, Infinitely running concurrents processes with loops from a geometric viewpoint, Elec. Notes Theor. Comput. Sci. 39 (2000) · Zbl 0976.68070
[9] R J van Glabbeek, On the expressiveness of higher dimensional automata, Theoret. Comput. Sci. 356 (2006) 265 · Zbl 1092.68071
[10] E Goubault, E Haucourt, Components of the fundamental category. II, Appl. Categ. Structures 15 (2007) 387 · Zbl 1131.55011
[11] M Grandis, Directed homotopy theory. II. Homotopy constructs, Theory Appl. Categ. 10 (2002) 369 · Zbl 1034.55006
[12] M Grandis, Directed homotopy theory. I, Cah. Topol. Géom. Différ. Catég. 44 (2003) 281 · Zbl 1059.55009
[13] M Grandis, Directed algebraic topology. Models of non-reversible worlds, New Math. Monogr. 13, Cambridge Univ. Press (2009) · Zbl 1176.55001
[14] J Gunawardena, Homotopy and concurrency, Bull. EATCS 54 (1994) 184 · Zbl 0938.68605
[15] M Herlihy, S Rajsbaum, Algebraic topology and distributed computing-a primer (editor J van Leeuwen), Lecture Notes in Comput. Sci. 1000, Springer (1995) 203 · Zbl 1374.68333
[16] J F Jardine, Path categories and resolutions, Preprint (2009) · Zbl 1203.55010
[17] T Kaczynski, K Mischaikow, M Mrozek, Computational homology, Applied Math. Sciences 157, Springer (2004) · Zbl 1039.55001
[18] T Kaczynski, M Mrozek, M Ślusarek, Homology computation by reduction of chain complexes, Comput. Math. Appl. 35 (1998) 59 · Zbl 0904.55004
[19] L Khachiyan, E Boros, K Elbassioni, V Gurvich, A new algorithm for the hypergraph transversal problem (editor L Wang), Lecture Notes in Comput. Sci. 3595, Springer (2005) 767 · Zbl 1128.05306
[20] D Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Math. 21, Springer (2008) · Zbl 1130.55001
[21] J Matou\vsek, G M Ziegler, Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Deutsch. Math.-Verein. 106 (2004) 71 · Zbl 1063.05047
[22] J Milnor, On spaces having the homotopy type of a \(\mathrm{CW}\)-complex, Trans. Amer. Math. Soc. 90 (1959) 272 · Zbl 0084.39002
[23] V Pratt, Modeling concurrency with geometry, 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 · Zbl 0961.68051
[25] M Raussen, Deadlocks and dihomotopy in mutual exclusion models, Theoret. Comput. Sci. 365 (2006) 247 · Zbl 1110.68089
[26] M Raussen, Invariants of directed spaces, Appl. Categ. Structures 15 (2007) 355 · Zbl 1134.55009
[27] M Raussen, Reparametrizations with given stop data, J. Homotopy Relat. Struct. 4 (2009) 1 · Zbl 1187.55007
[28] M Raussen, Trace spaces in a pre-cubical complex, Topology Appl. 156 (2009) 1718 · Zbl 1165.55006
[29] M Raussen, Simplicial models for trace spaces, Tech. Report R-2010-02, Dept. of Math. Sciences, Aalborg University (2010) · Zbl 1198.55004
[30] G Winskel, M Nielsen, Models for concurrency (editors S Abramsky, D M Gabbay, T S E Maibaum), Handb. Log. Comput. Sci. 4, Oxford Univ. Press (1995) 1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.