Geodesic
Simplicial models for trace spaces II: General higher dimensional automata
Raussen, Martin1
1Department of Mathematical Sciences, Aalborg University, Fredrik Bajersvej 7G, DK-9220 Aalborg Øst, Denmark
Algebraic and Geometric Topology, Tome 12 (2012) no. 3, pp. 1741-1761
Cet article a éte moissonné depuis la source Mathematical Sciences Publishers

Voir la notice de l'article

Higher Dimensional Automata (HDA) are topological models for the study of concurrency phenomena. The state space for an HDA is given as a pre-cubical complex in which a set of directed paths (d-paths) is singled out. The aim of this paper is to describe a general method that determines the space of directed paths with given end points in a pre-cubical complex as the nerve of a particular category.

The paper generalizes the results from Raussen [Algebr. Geom. Topol. 10 (2010) 1683–1714; Appl. Algebra Engrg. Comm. Comput. 23 (2012) 59–84] in which we had to assume that the HDA in question arises from a semaphore model. In particular, important for applications, it allows for models in which directed loops occur in the processes involved.

DOI : 10.2140/agt.2012.12.1741
Classification : 55P10, 55P15, 55U10, 68Q85, 68Q55
Keywords: higher dimensional automata, execution path, poset category, directed loop, arc length, covering, homotopy equivalence

Raussen, Martin  1

1 Department of Mathematical Sciences, Aalborg University, Fredrik Bajersvej 7G, DK-9220 Aalborg Øst, Denmark 
@article{10_2140_agt_2012_12_1741,
     author = {Raussen, Martin},
     title = {Simplicial models for trace spaces {II:} {General} higher dimensional automata},
     journal = {Algebraic and Geometric Topology},
     pages = {1741--1761},
     year = {2012},
     volume = {12},
     number = {3},
     doi = {10.2140/agt.2012.12.1741},
     url = {http://geodesic.mathdoc.fr/articles/10.2140/agt.2012.12.1741/}
}
TY  - JOUR
AU  - Raussen, Martin
TI  - Simplicial models for trace spaces II: General higher dimensional automata
JO  - Algebraic and Geometric Topology
PY  - 2012
SP  - 1741
EP  - 1761
VL  - 12
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.2140/agt.2012.12.1741/
DO  - 10.2140/agt.2012.12.1741
ID  - 10_2140_agt_2012_12_1741
ER  - 
%0 Journal Article
%A Raussen, Martin
%T Simplicial models for trace spaces II: General higher dimensional automata
%J Algebraic and Geometric Topology
%D 2012
%P 1741-1761
%V 12
%N 3
%U http://geodesic.mathdoc.fr/articles/10.2140/agt.2012.12.1741/
%R 10.2140/agt.2012.12.1741
%F 10_2140_agt_2012_12_1741
Raussen, Martin. Simplicial models for trace spaces II: General higher dimensional automata. Algebraic and Geometric Topology, Tome 12 (2012) no. 3, pp. 1741-1761. doi: 10.2140/agt.2012.12.1741

[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] P Bubenik, Simplicial models for concurrency, from: "Proceedings of the workshop on Geometric and Topological Methods in Computer Science", Electronic Notes in Theoretical Comp. Sci. 283 (2012) 3

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

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

[6] L Fajstrup, Dipaths and dihomotopies in a cubical complex, Adv. in Appl. Math. 35 (2005) 188

[7] L Fajstrup, Trace spaces of directed tori with rectangular holes, Tech. Report R-2011-08, Department of Math. Sciences, Aalborg University (2011)

[8] L Fajstrup, É Goubault, E Haucourt, S Mimran, M Raussen, Trace spaces: An efficient new technique for state-space reduction, from: "European Symposium on Programming 2012" (editor H Seidl), Lecture Notes in Comp. Sci. 7211, Springer (2012) 274

[9] L Fajstrup, M Raußen, E Goubault, Algebraic topology and concurrency, Theoret. Comput. Sci. 357 (2006) 241

[10] M Farber, Zeros of closed $1$–forms, homoclinic orbits and Lusternik–Schnirelman theory, Topol. Methods Nonlinear Anal. 19 (2002) 123

[11] M Farber, Topology of closed one-forms, Math. Surveys and Monogr. 108, Amer. Math. Soc. (2004)

[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, New Math. Monogr. 13, Cambridge Univ. Press (2009)

[14] D Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Math. 21, Springer (2008)

[15] V Pratt, Modelling concurrency with geometry, from: "Proc. of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages" (editor D Wise), ACM (1991) 311

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

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

[18] M Raussen, Simplicial models of trace spaces, Algebr. Geom. Topol. 10 (2010) 1683

[19] M Raussen, Execution spaces for simple higher dimensional automata, Appl. Algebra Engrg. Comm. Comput. 23 (2012) 59

[20] C P Rourke, B J Sanderson, $\triangle $–sets I: Homotopy theory, Quart. J. Math. Oxford Ser. 22 (1971) 321

[21] D Sullivan, Infinitesimal computations in topology, Inst. Hautes Études Sci. Publ. Math. (1977) 269

[22] R J Van Glabbeek, Erratum to: \hspace-2pt“On the expressiveness of higher dimensional automata” \rm[Theoret. Comput. Sci. 356 (2006) 265–290 \xoxMR2223695], Theoret. Comput. Sci. 368 (2006) 168

[23] 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), Oxford Univ. Press (1995) 1

Cité par Sources :