Towards Directed Collapsibility

While collapsibility of CW complexes dates back to the 1930s, collapsibility of directed complexes has not been well studied to date. We define a notion of directed collapsibility in the setting of a directed Euclidean cubical complex that builds on theclassical definition of collapsibility. We call this type of collapse a link-preserving directed collapse. In the undirected setting, pairs of cells are removed from a space if a deformation retract remains. In the directed setting, topological properties - in particular, properties of spaces of directed paths - would not always be preserved. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We show that there are computationally simple conditions which preserve the topology of past links. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of spaces of directed paths. Our results have applications to speeding up the verification process of concurrent programming and to understanding partial executions in concurrent programs. This is joint work with Robin Belton, Robyn Brooks, Stefania Ebli, Lisbeth Fajstrup, Brittany Terese Fasy, and Nicole Sanderson.