Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T12:05:12.840Z Has data issue: false hasContentIssue false
  • English
  • Français

Strictifying and taming directed paths in Higher Dimensional Automata

Published online by Cambridge University Press:  15 September 2021

Martin Raussen Open the ORCID record for Martin Raussen [Opens in a new window]
Martin Raussen*
Affiliation:
Department of Mathematical Sciences, Aalborg University, Skjernvej 4A, Aalborg Øst DK-9220, Denmark Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Directed paths have been used by several authors to describe concurrent executions of a program. Spaces of directed paths in an appropriate state space contain executions with all possible legal schedulings. It is interesting to investigate whether one obtains different topological properties of such a space of executions if one restricts attention to schedulings with “nice” properties, e.g. involving synchronisations. This note shows that this is not the case, i.e. that one may operate with nice schedulings without inflicting any harm. Several of the results in this note had previously been obtained by Ziemiański in Ziemiański (2017. Applicable Algebra in Engineering, Communication and Computing28 497–525; 2020a. Journal of Applied and Computational Topology4 (1) 45–78). We attempt to make them accessible for a wider audience by giving an easier proof for these findings by an application of quite elementary results from algebraic topology; notably the nerve lemma.

Keywords

Higher Dimensional Automatad-pathstricttameserialparallelhomotopy equivalencenerve lemma
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 31 , Issue 2 , February 2021 , pp. 193 - 213
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The author thanks Uli Fahrenberg (École Polytechnique, Paris) and Krzysztof Ziemiański (Warsaw) for helpful conversations; Ziemiański particularly for pointing out several uncorrect statements in previous versions. Thanks are also due to the anonymous referees for several hints leading to improvements of the presentation.

References

Björner, A. A. (1995). Topological methods. In: Graham, R. L., Grötschel, M., Lovàsz, L. (eds.), Handbook of Combinatorics, vol. 1-2, Elsevier (North-Holland), Amsterdam, 18191872.Google Scholar
Borsuk, K. (1948). On the imbedding of systems of compacta in simplicial complexes. Fundamenta Mathematicae 35 217–234.CrossRefGoogle Scholar
Dubut, J. (2019). Trees in partial higher dimensional automata. In: Bojańczyk, M. and Simpson, A. (eds.), Foundations of Software Science and Computation Structures, Springer, 224–241.CrossRefGoogle Scholar
Fahrenberg, U., Johansen, Ch., Struth, G. and Thapa, R. B. (2020). Generating posets beyond N. In: Relational and Algebraic Methods in Computer Science - Proceedings of the 18th International Conference, RAMiCS 2020, Palaiseau, France, Lecture Notes in Computer Science, vol. 12062, 82–99.CrossRefGoogle Scholar
Fahrenberg, U. and Legay, A. (2015). Partial higher-dimensional automata. In: CALCO, 101–115.Google Scholar
Fajstrup, L., Goubault, É., Haucourt, E., Mimram, S. and Raussen, M. (2016). Directed Algebraic Topology and Concurrency, Springer.CrossRefGoogle Scholar
Fajstrup, L., Goubault, É. and Raussen, M. (2006). Algebraic topology and concurrency. Theoretical Computer Science 357 241–278, Revised version of Aalborg University preprint, 1999.CrossRefGoogle Scholar
Fanchon, J. and Morin, R. (2009). Pomset languages of finite step transition systems. In: Proceedings of the Applications and Theory of Petri Nets 2009, Lecture Notes in Computer Science, vol. 5606, 83–102.CrossRefGoogle Scholar
Grandis, M. (2003). Directed homotopy theory I. The fundamental category. Cahiers de Topologie et Géométrie Différentielle Catégoriques 44 281–316.Google Scholar
Grandis, M. (2009). Directed Algebraic Topology. Models of Non-Reversible Worlds, New Mathematical Monographs, vol. 13, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Hatcher, A. (2002). Algebraic Topology, Cambridge University Press.Google Scholar
Hovey, M. (1999). Model Categories, Mathematical Surveys and Monographs, vol. 63, American Mathematical Society.Google Scholar
Kozlov, D. (2008). Combinatorial Algebraic Topology, Springer.CrossRefGoogle Scholar
Leray, J. (1945). Sur la forme des espaces topologiques et sur les points fixes des représentations. Journal de Mathématiques Pures et Appliquées 24 95–167.Google Scholar
McCord, M. C. (1967). Homotopy type comparison of a space with complexes associated with its open covers. Proceedings of the American Mathematical Society 18 705–708.CrossRefGoogle Scholar
Pratt, V. (1991). Modelling concurrency with geometry. In: Proceedings of the 18th ACM Symposium on Principles of Programming Languages, 311–322.Google Scholar
Quillen, D. (1972). Higher algebraic K-theory. I. In: Algebraic K-Theory, I: Higher K-Theories, Proceedings of the Conference, Battelle Memorial Institute, Seattle, Washington, 1972, Lecture Notes in Mathematics, vol. 341, 85–147.Google Scholar
Raussen, M. (2009). Trace spaces in a pre-cubical complex. Topology and Its Applications 156 1718–1728.CrossRefGoogle Scholar
Raussen, M. and Ziemiański, K. (2014). Homology of spaces of directed paths on Euclidean cubical complexes. Journal of Homotopy and Related Structures 9 67–84.CrossRefGoogle Scholar
van Glabbeek, R. (1991). Bisimulation Semantics for Higher Dimensional Automata. Technical report, Stanford University.Google Scholar
van Glabbeek, R. (2006). On the expressiveness of higher dimensional automata. Theoretical Computer Science 368 (1–2) 168–194.CrossRefGoogle Scholar
Weil, A. (1952). Sur les théorèmes de de Rham. Commentarii Mathematici Helvetici 26 119–145.CrossRefGoogle Scholar
Ziemiański, K. (2017). Spaces of directed paths on pre-cubical sets. Applicable Algebra in Engineering, Communication and Computing 28 497–525.CrossRefGoogle Scholar
Ziemiański, K. (2020a). Spaces of directed paths on pre-cubical sets II. Journal of Applied and Computational Topology 4 (1) 45–78.CrossRefGoogle Scholar
Ziemiański, K. (2020b). Private Communication.Google Scholar