No CrossRef data available.
Article contents
Strictifying and taming directed paths in Higher Dimensional Automata
Published online by Cambridge University Press: 15 September 2021
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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 Computing 28 497–525; 2020a. Journal of Applied and Computational Topology 4 (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.
Information
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2021. Published by Cambridge University Press
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
Hovey, M. (1999). Model Categories, Mathematical Surveys and Monographs, vol. 63, American Mathematical Society.Google 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
You have
Access
- 2
- Cited by