Topological deformation of higher dimensional automata

Philippe Gaucher ; Eric Goubault

Homology, homotopy, and applications, Tome 5 (2003) no. 2, pp. 39-82.

Résumé

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 [6]) which model concurrent systems in computer science. It is known [11] 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 [11]. 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.

Détail

DOI : 10.4310/HHA.2003.v5.n2.a3

Classification : 55P15, 55U05, 68Q85
Keywords: homology, homotopy, concurrency, cubical set, CW-complex, higher dimensional automata, category, localization, partial order, partially ordered space