preprint : Topological Deformation of Higher Dimensional Automata
Title : Topological Deformation of Higher Dimensional Automata Authors : Philippe Gaucher, Eric Goubault 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. Globular CW-complexes are designed to be to local po-spaces what CW-complexes are to topological spaces. 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. Url : http://www-irma.u-strasbg.fr/~gaucher/diCW.ps http://www-irma.u-strasbg.fr/~gaucher/diCW.ps.gz http://www-irma.u-strasbg.fr/~gaucher/diCW.pdf http://www-irma.u-strasbg.fr/~gaucher/diCW.pdf.gz Comments : 44 pages, LaTeX2e + figures
participants (1)
-
Philippe Gaucher