Directed algebraic topology

Many mathematical definitions have been proposed to formalise the notion of directed space. E. W. Dijkstra introduced a simple dialect to deal with semaphores, the so-called 'PV language',[2] and to provide each PV program an abstract model: its 'geometric semantics'. Any such model admits a natural partially ordered space (or pospace) structure i.e. a topology and a partial order.[3] The points of the model should be thought of as the states of the program and the partial order as the 'causality' relation between states. Following this approach, the directed paths over the model i.e. the monotonic continuous paths, represent the execution traces of the program. From the computer science point of view, however, the resulting pospaces have a severe drawback. Because partial orders are by definition antisymmetric, their only directed loops i.e. directed paths which end where they start, are the constant loops.

Inspired by smooth manifolds, L. Fajstrup, E. Goubault, and M. Raussen use the sheaf-theoretic approach to define local pospaces.[4] Roughly speaking, a local pospace is a topological space together with an open covering whose elements are endowed with a partial order. Given two elements U and V of the covering, it is required that the partial orders on U and V match on the intersection. Though local pospaces allow directed loops, they form a category whose colimits—when they exist—may be rather ill-behaved.

Noting that the directed paths of a (local) pospace appear as a by-product of the (local) partial order—even though they themselves contain most of the relevant information about direction—Marco Grandis defines d-spaces[5] as topological spaces endowed with a collection of paths, whose members are said to be directed, such that any constant path is directed, the concatenation of two directed paths is still directed, and any subpath of a directed path is directed. D-spaces admit non-constant directed loops and form a category enjoying properties similar to the ones enjoyed by the category of topological spaces.

As shown by Sanjeevi Krishnan, the drawbacks of local pospaces can be avoided if we extend the notion of pospaces by means of 'cosheaves'. The notion of stream[6] is defined thus. More precisely one considers preorders on open subsets and one requires that given any open subset U and any open covering Ω of U, the preorder associated with U is 'generated' by the preorders associated with each member of Ω. The resulting category behaves as nicely as the category of d-spaces. Indeed, both of them one can define the directed geometric realization of cubical set (simplicial set) so that its underlying topological space is the (usual) geometric realisation. In fact there is a natural embedding G of the category of streams into the category of d-spaces. This embedding admits a left adjoint functor F. The images of F and G are isomorphic, an isomorphism being obtained by restricting F and G to those images. The category of d-spaces can thus be seen as one of the most general formalisations of the intuitive notion of directed space.

Regardless of the kind of directed space on considers (pospaces, local pospaces, d-spaces or streams) there is an obvious forgetful functor to the category of topological spaces. Given two directed paths γ and δ, a directed homotopy from γ to δ is a morphism of directed spaces h whose underlying map U(h) is a homotopy –in the usual sense– between the underlying path (topology) U(γ) and U(δ). In algebraic topology, there is a homotopy from α to β if and only if there is a homotopy from β to α. Due to non-reversibility, this is no longer true for directed homotopies. As a consequence, we define the congruence ${\displaystyle \sim }$ as the least equivalence relation on the directed paths which is compatible with concatenation and relates γ to δ as soon as there is a directed homotopy from γ to δ. Going back to the computer science motivation where directed paths represent execution traces, directed homotopies provide a way to identify execution traces. Hence, given a directed space X which models some concurrent program P, the topology of X can be seen as the 'local commutations' of actions in the program P. In classical models of concurrency like 'asynchronous graphs' of 'Mazurkiewicz traces', the local commutations are provided by a relation over the arrows or the actions.

The fundamental category of a directed space is defined by mimicking the construction of the fundamental groupoid[7][8] of a topological space. More precisely given a directed space ${\displaystyle X}$, we consider the (small) category ${\displaystyle DX}$ of directed paths over ${\displaystyle X}$ up to monotonic reparametrisation[9] and define the fundamental category of ${\displaystyle X}$ as the quotient ${\displaystyle \pi _{1}(X)\$ :=\ DX/\sim } . This construction gives rise to a functor ${\displaystyle \pi _{1}}$ from the category of directed spaces to the category of small categories.

While the fundamental category construction drastically reduces the size of the homsets of DX, it leaves its collection of objects unchanged. And yet, if X is the geometric model of some concurrent program P, this collection is uncountable. The category of components was introduced to find a full subcategory of the fundamental category with as few objects as possible though it contains all the relevant information from the original.[10] If ${\displaystyle C}$ is a loop-free category, then its category of components ${\displaystyle \pi _{0}(C)}$ can be described in the language of category theory without assuming ${\displaystyle C}$ is the fundamental category of some directed space. In this case the intuitive notion of insignificant morphisms is formalised as a collection ${\displaystyle \Sigma }$ of morphisms of ${\displaystyle C}$ satisfying some stability properties and whose elements both preserve the past of their source and the future of their target. Then ${\displaystyle \pi _{0}(C)}$ is defined as the quotient[11] ${\displaystyle C/\Sigma }$ which is proven to be equivalent to the localization of a category ${\displaystyle C[\Sigma ^{-1}]}$.[12] The category of components of a PV program P is then defined as ${\displaystyle \pi _{0}(\pi _{1}(X))}$ where ${\displaystyle X}$ is the geometric model of P. As an interesting property, the category of components of any PV program is finite.

• Directed Algebraic Topology and Concurrency, Lisbeth Fajstrup, Éric Goubault, Samuel Mimram, Emmanuel Haucourt, Martin Raussen
• Directed homotopy theory, II. Homotopy Constructs, Marco Grandis, Theory and Applications of Categories, Vol. 10, No. 14, 2002, pp. 369–391
• A Few Points On Directed Algebraic Topology, Marco Grandis
• Directed combinatorial homology and noncommutative tori, Marco Grandis, Math. Proc. Cambridge Philos. Soc. 138 (2005), 233-262