Topological Deformation of Higher Dimensional Automata

Abstract

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 which model concurrent systems in computer science. It is known 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. 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.

43 pages ; LaTeX2e ; 12 postscript figures ; final version to appear in Homology, Homotopy and Applications

Cited by in corpus (4)

• Combinatorics of labelling in higher dimensional automata
• T-homotopy and refinement of observation (I) : Introduction
• T-homotopy and refinement of observation (II) : Adding new T-homotopy equivalences
• Some collapsing operations for 2-dimensional precubical sets