Some collapsing operations for 2-dimensional precubical sets

DOI10.1007/S40062-012-0010-7MaRDI QIDQ691262zbMATH OpenOpenAlexFDO

Authors Thomas Kahl

Publication date 30 November 2012

Published in Journal of Homotopy and Related Structures (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.5443

zbMATH Keywords

\(d\)-spacesconcurrency theorydirected homotopy theoryfundamental bipartite graphfundamental categoryprecubical setstrace spaces

Mathematics Subject Classification ID

Homotopy equivalences in algebraic topology (55P10) Homotopy theory (55P99) Applied homological algebra and category theory in algebraic topology (55U99) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: In this paper, we consider 2-dimensional precubical sets, which can be used to model systems of two concurrently executing processes. From the point of view of concurrency theory, two precubical sets can be considered equivalent if their geometric realizations have the same directed homotopy type relative to the extremal elements in the sense of P. Bubenik. We give easily verifiable conditions under which it is possible to reduce a 2-dimensional precubical set to an equivalent smaller one by collapsing an edge or eliminating a square and one or two free faces. We also look at some simple standard examples in order to illustrate how our results can be used to construct small models of 2-dimensional precubical sets.

Review text

Precubical sets are used to model concurrent systems, an \(n\)-cube modelling the concurrent execution of \(n\) actions. They can be realized as \(d\)-spaces in the sense of Grandis. In this paper, two precubical sets have the same directed homotopy type if the associated \(d\)-spaces are dihomotopic in Grandis' sense with respect to the extremal elements in the sense of Bubenik. The author gives rules to reduce the size of a \(2\)-dimensional precubical set so that the new one has the same directed homotopy type. These rules consist of collapsing an edge or eliminating a square and one or two free faces if some conditions are satisfied. This kind of results is important to face the combinatorial explosion caused by the real models coming from computer science.

Recommendations

• Comparing equivalences on precubical sets and spaces
• The homology graph of a precubical set
• Spaces of directed paths on pre-cubical sets
• Spaces of directed paths on pre-cubical sets II
• Topological abstraction of higher-dimensional automata

Cites work

• Algebraic topology and concurrency
• Components of the fundamental category
• Components of the fundamental category. II
• Dipaths and dihomotopies in a cubical complex
• Directed algebraic topology. Models of non-reversible worlds
• Invariants of directed spaces
• Models and van Kampen theorems for directed homotopy theory
• On the expressiveness of higher dimensional automata
• Reparametrizations of continuous paths
• Some geometric perspectives in concurrency theory
• Topological deformation of higher dimensional automata
• Trace spaces in a pre-cubical complex

Cited in

(5)

• Computing path categories of finite directed cubical complexes
• The homology graph of a precubical set
• Topological abstraction of higher-dimensional automata
• Comparing equivalences on precubical sets and spaces
• Directed homotopy in non-positively curved spaces

This page was built for publication: Some collapsing operations for 2-dimensional precubical sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q691262)