Topological Deformation of Higher Dimensional Automata

Philippe Gaucher and Eric Goubault

A local po-space is a gluing of topological spaces which are equipped with a closed partial ordering representing the time flow. They are used as a formalization of higher dimensional automata (see for instance \cite{LFEGMRAlgebraic}) which model concurrent systems in computer science. It is known \cite{ConcuToAlgTopo} that there are two distinct notions of deformation of higher dimensional automata, ``spatial'' and ``temporal'', leaving invariant computer scientific properties like presence or absence of deadlocks. Unfortunately, the formalization of these notions is still unknown in the general case of local po-spaces. We introduce here a particular kind of local po-space, the ``globular CW-complexes'', for which we formalize these notions of deformations and which are sufficient to formalize higher dimensional automata. The existence of the category of globular CW-complexes was already conjectured in \cite{ConcuToAlgTopo}. After localizing the category of globular CW-complexes by spatial and temporal deformations, we get a category (the category of dihomotopy types) whose objects up to isomorphism represent exactly the higher dimensional automata up to deformation. Thus globular CW-complexes provide a rigorous mathematical foundation to study from an algebraic topology point of view higher dimensional automata and concurrent computations.

Homology, Homotopy and Applications, Vol. 5(2003), No. 2, pp. 39-82

Available as: dvi dvi.gz ps ps.gz pdf figures