Spaces of directed paths as simplicial complexes

Concurrency theory in Computer Science studies the effects that arise when several processors run simultaneously sharing common resources. It attempts to advise methods to deal with the “state space explosion problem”, sometimes using models with a combinatorial/topological flavor. It is a common feature of these models that an execution corresponds to a directed path (d-path), and that d-homotopies (preserving the directions) have equivalent computations as a result.

I will discuss particular classical examples of directed spaces, a class of Higher Dimensional Automata (HDA). For such a space, I will describe a (nerve lemma) method that determines the homotopy type of the space of traces (executions) as a prodsimplicial complex – with products of simplices as building blocks. A description of that complex opens up

for (machine) calculations of homology groups and other topological invariants of the trace space. The determination of path components is particularly important for applications.

This method leads to an algorithm yielding a representation of the prodsimplicial complex and implemented using the French ALCOOL software and allowing calculations of homological invariants using homology software by Mrozek et al.

Unfortunately, the resulting prodsimplicial complexes grow quickly in both dimension and the number of cells. I shall sketch ongoing work with K. Ziemianski that tries to overcome this drawback by finding smaller homotopy equivalent simplicial complexes via suitable homotopy decompositions of path spaces.