Higher dimensional transition systems

The electronic files available here are either in prepublication form (ArXiv), or as published if the journal allows this, provided that a hyperlink towards the journal is added. In all cases, the authoritative version is the one of the journal.

Philippe Gaucher. Towards a homotopy theory of higher dimensional transition systems (PS,PDF,BIB), Theory and Applications of Categories, vol. 25, 295-341, 2011.

We proved in a previous work that Cattani-Sassone's higher dimensional transition systems can be interpreted as a small-orthogonality class of a topological locally finitely presentable category of weak higher dimensional transition systems. In this paper, we turn our attention to the full subcategory of weak higher dimensional transition systems which are unions of cubes. It is proved that there exists a left proper combinatorial model structure such that two objects are weakly equivalent if and only if they have the same cubes after simplification of the labelling. This model structure is obtained by Bousfield localizing a model structure which is left determined with respect to a class of maps which is not the class of monomorphisms. We prove that the higher dimensional transition systems corresponding to two process algebras are weakly equivalent if and only if they are isomorphic. We also construct a second Bousfield localization in which two bisimilar cubical transition systems are weakly equivalent. The appendix contains a technical lemma about smallness of weak factorization systems in coreflective subcategories which can be of independent interest. This paper is a first step towards a homotopical interpretation of bisimulation for higher dimensional transition systems.

Philippe Gaucher. Directed algebraic topology and higher dimensional transition systems (PDF,BIB). New-York Journal of Mathematics 16 (2010), 409-461.

Cattani-Sassone's notion of higher dimensional transition system is interpreted as a small-orthogonality class of a locally finitely presentable topological category of weak higher dimensional transition systems. In particular, the higher dimensional transition system associated with the labelled n-cube turns out to be the free higher dimensional transition system generated by one n-dimensional transition. As a first application of this construction, it is proved that a localization of the category of higher dimensional transition systems is equivalent to a locally finitely presentable reflective full subcategory of the category of labelled symmetric precubical sets. A second application is to Milner's calculus of communicating systems (CCS): the mapping taking process names in CCS to flows is factorized through the category of higher dimensional transition systems. The method also applies to other process algebras and to topological models of concurrency other than flows.

Flows over space and cubes

Philippe Gaucher. Combinatorics of labelling in higher dimensional automata (PS,PDF,BIB), ArXiv, Theoretical Computer Science (2010), 411(11-13), pp 1452-1483, doi:10.1016/j.tcs.2009.11.013. Final PDF version available on request.

The main idea for interpreting concurrent processes as labelled precubical sets is that a given set of n actions running concurrently must be assembled to a labelled n-cube, in exactly one way. The main ingredient is the non-functorial construction called labelled directed coskeleton. It is defined as a subobject of the labelled coskeleton, the latter coinciding in the unlabelled case with the right adjoint to the truncation functor. This non-functorial construction is necessary since the labelled coskeleton functor of the category of labelled precubical sets does not fulfil the above requirement. We prove in this paper that it is possible to force the labelled coskeleton functor to be well-behaved by working with labelled transverse symmetric precubical sets. Moreover, we prove that this solution is the only one. A transverse symmetric precubical set is a precubical set equipped with symmetry maps and with a new kind of degeneracy map called transverse degeneracy. Finally, we also prove that the two settings are equivalent from a directed algebraic topological viewpoint. To illustrate, a new semantics of CCS, equivalent to the old one, is given.

Philippe Gaucher. Towards a homotopy theory of process algebra (PS,PDF,BIB), Homology, Homotopy and Applications, vol. 10 (1):p.353-388, 2008.

This paper proves that labelled flows are expressive enough to contain all process algebras which are a standard model for concurrency. More precisely, we construct the space of execution paths and of higher dimensional homotopies between them for every process name of every process algebra with any synchronization algebra using a notion of labelled flow. This interpretation of process algebra satisfies the paradigm of higher dimensional automata (HDA): one non-degenerate full $n$-dimensional cube (no more no less) in the underlying space of the time flow corresponding to the concurrent execution of $n$ actions. This result will enable us in future papers to develop a homotopical approach of process algebras. Indeed, several homological constructions related to the causal structure of time flow are possible only in the framework of flows.

Philippe Gaucher. Globular realization and cubical underlying homotopy type of time flow of process algebra (PS,PDF,BIB). New-York Journal of Mathematics 14 (2008), 101-137.

We construct a small realization as flow of every precubical set (modeling for example a process algebra). The realization is small in the sense that the construction does not make use of any cofibrant replacement functor and of any transfinite construction. In particular, if the precubical set is finite, then the corresponding flow has a finite globular decomposition. Two applications are given. The first one presents a realization functor from precubical sets to globular complexes which is characterized up to a natural S-homotopy. The second one proves that, for such flows, the underlying homotopy type is naturally isomorphic to the homotopy type of the standard cubical complex associated with the precubical set.

Flows over space and globular complex

Philippe Gaucher. Homotopical interpretation of globular complex by multipointed d-space (PS,PDF,BIB), Theory and Applications of Categories, vol. 22, 588-621, 2009.

Globular complexes were introduced by E. Goubault and the author to model higher dimensional automata. Globular complexes are topological spaces equipped with a globular decomposition which is the directed analogue of the cellular decomposition of a CW-complex. We prove that there exists a combinatorial model category such that the cellular objects are exactly the globular complexes and such that the homotopy category is equivalent to the homotopy category of flows. The underlying category of this model category is a variant of M. Grandis' notion of d-space over a topological space colimit generated by simplices. This result enables us to understand the relationship between the framework of flows and other works in directed algebraic topology using d-spaces. It also enables us to prove that the underlying homotopy type functor of flows can be interpreted up to equivalences of categories as the total left derived functor of a left Quillen adjoint.

Philippe Gaucher. T-homotopy and refinement of observation (I) : Introduction (PS,PDF,BIB) Electronic Notes in Theoretical Computer Sciences 230 (2009), 103-110. (GETCO 2005).

This paper is the extended introduction of a series of papers about modelling T-homotopy by refinement of observation. The notion of T-homotopy equivalence is discussed. A new one is proposed and its behaviour with respect to other construction in dihomotopy theory is explained. We also prove in appendix that the tensor product of flows is a closed symmetric monoidal structure.

Note: the version published in ENTCS is the wrong one !! Please download this one which is a better abstract with an up-to-date bibliography.

Philippe Gaucher. T-homotopy and refinement of observation (II) : Adding new T-homotopy equivalences (PDF,BIB), pusblished in the Internat. J. Math. Math. Sci., Article ID 87404, 20 pages (2007).

This paper is the second part of a series of papers about a new notion of T-homotopy of flows. It is proved that the old definition of T-homotopy equivalence does not allow the identification of the directed segment with the $3$-dimensional cube. This contradicts a paradigm of dihomotopy theory. A new definition of T-homotopy equivalence is proposed, following the intuition of refinement of observation. And it is proved that up to weak S-homotopy, a old T-homotopy equivalence is a new T-homotopy equivalence. The left-properness of the weak S-homotopy model category of flows is also established in this second part. The latter fact is used several times in the next papers of this series.

Philippe Gaucher. T-homotopy and refinement of observation (III) : Invariance of the branching and merging homologies (PS,PDF,BIB). New-York Journal of Mathematics 12 (2006), 319-348.

This series explores a new notion of T-homotopy equivalence of flows. The new definition involves embeddings of finite bounded posets preserving the bottom and the top elements and the associated cofibrations of flows. In this third part, it is proved that the generalized T-homotopy equivalences preserve the branching and merging homology theories of a flow. These homology theories are of interest in computer science since they detect the nondeterministic branching and merging areas of execution paths in the time flow of a higher-dimensional automaton. The proof is based on Reedy model category techniques.

Philippe Gaucher. T-homotopy and refinement of observation (IV) : Invariance of the underlying homotopy type (PS,PDF,BIB). New-York Journal of Mathematics 12 (2006), 63-95.

Philippe Gaucher. Inverting weak dihomotopy equivalence using homotopy continuous flow (PS,PDF,BIB), Theory and Applications of Categories, vol. 16, 59-83, 2006.

A flow is homotopy continuous if it is indefinitely divisible up to S-homotopy. The full subcategory of cofibrant homotopy continuous flows has nice features. Not only it is big enough to contain all dihomotopy types, but also a morphism between them is a weak dihomotopy equivalence if and only if it is invertible up to dihomotopy. Thus, the category of cofibrant homotopy continuous flows provides an implementation of Whitehead's theorem for the full dihomotopy relation, and not only for S-homotopy as in previous works of the author. This fact is not the consequence of the existence of a model structure on the category of flows because it is known that there does not exist any model structure on it whose weak equivalences are exactly the weak dihomotopy equivalences. This fact is an application of a general result for the localization of a model category with respect to a weak factorization system.

Erratum : the class of morphisms L must be of course a subclass of the class of monomorphisms for Proposition 3.18 to be true.

Philippe Gaucher. Flow does not model flows up to weak dihomotopy (PS,PDF,BIB), ArXiv. Applied Categorical Structures, vol. 13, p. 371-388 (2005).

We prove that the category of flows cannot be the underlying category of a model category whose corresponding homotopy types are the flows up to weak dihomotopy. Some hints are given to overcome this problem. In particular, a new approach of dihomotopy involving simplicial presheaves over an appropriate small category is proposed. This small category is obtained by taking a full subcategory of a locally presentable version of the category of flows.

Philippe Gaucher. Homological properties of non-deterministic branchings and mergings in higher dimensional automata (PS,PDF,BIB), Homology, Homotopy and Applications, vol. 7 (1):p.51-76, 2005.

The branching (resp. merging) space functor of a flow is a left Quillen functor. The associated derived functor allows to define the branching (resp. merging) homology of a flow. It is then proved that this homology theory is a dihomotopy invariant and that higher dimensional branchings (resp. mergings) satisfy a long exact sequence.

Philippe Gaucher. Comparing globular complex and flow (PS,PDF,BIB). New-York Journal of Mathematics 11 (2005), 97-150.

A functor is constructed from the category of globular CW-complexes to that of flows. It allows the comparison of the S-homotopy equivalences (resp. the T-homotopy equivalences) of globular complexes with the S-homotopy equivalences (resp. the T-homotopy equivalences) of flows. Moreover, it is proved that this functor induces an equivalence of categories from the localization of the category of globular CW-complexes with respect to S-homotopy equivalences to the localization of the category of flows with respect to weak S-homotopy equivalences. As an application, we construct the underlying homotopy type of a flow.

Philippe Gaucher. The homotopy branching space of a flow, Electronic Notes in Theoretical Computer Science vol. 100 : pp 95-109, 2004 (PS,PDF,BIB). Extended abstract of a talk given at GETCO 2003.

In this talk, I will explain the importance of the homotopy branching space functor (and of the homotopy merging space functor) in dihomotopy theory. Note : the definition of T-homotopy equivalence given in this talk is now obsolete : it is conjecturally too big.

Philippe Gaucher. A model category for the homotopy theory of concurrency (PS,PDF,BIB), Homology, Homotopy and Applications, vol. 5 (1):p.549-599, 2003.

We construct a cofibrantly generated model structure on the category of flows such that any flow is fibrant and such that two cofibrant flows are homotopy equivalent for this model structure if and only if they are S-homotopy equivalent. This result provides an interpretation of the notion of S-homotopy equivalence in the framework of model categories.

Philippe Gaucher. Concurrent Process up to Homotopy (II) (PS,PDF,BIB). C. R. Acad. Sci. Paris Ser. I Math., 336(8):647-650, 2003 (French).

On démontre que la catégorie des CW-complexes globulaires à dihomotopie près est équivalente à la catégorie des flots à dihomotopie faible près. Ce théorème est une généralisation du théorème classique disant que la catégorie des CW-complexes modulo homotopie est équivalente à la catégorie des espaces topologiques modulo homotopie faible.
One proves that the category of globular CW-complexes up to dihomotopy is equivalent to the category of flows up to weak dihomotopy. This theorem generalizes the classical theorem which states that the category of CW-complexes up to homotopy is equivalent to the category of topological spaces up to weak homotopy.

Philippe Gaucher. Concurrent Process up to Homotopy (I) (PS,PDF,BIB). C. R. Acad. Sci. Paris Ser. I Math., 336(7):593-596, 2003 (French).

Les CW-complexes globulaires et les flots sont deux modélisations géométriques des automates parallèles qui permettent de formaliser la notion de dihomotopie. La dihomotopie est une relation d'équivalence sur les automates parallèles qui préserve des propriétés informatiques comme la présence ou non de deadlock. On construit un plongement des CW-complexes globulaires dans les flots et on démontre que deux CW-complexes globulaires sont dihomotopes si et seulement si les flots associés sont dihomotopes.
Globular CW-complexes and flows are both geometric models of concurrent processes which allow to model in a precise way the notion of dihomotopy. Dihomotopy is an equivalence relation which preserves computer-scientific properties like the presence or not of deadlock. One constructs an embedding from globular CW-complexes to flows and one proves that two globular CW-complexes are dihomotopic if and only if the corresponding flows are dihomotopic.

Globular complex and local po-space

Philippe Gaucher, Eric Goubault. Topological Deformation of Higher Dimensional Automata (PS,PDF,BIB), Homology, Homotopy and Applications, vol. 5 (2):p.39-82, 2003.

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. The existence of the category of globular CW-complexes was already conjectured in From Concurrency to Algebraic Topology. 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.

Philippe Gaucher, Investigating The Algebraic Structure of Dihomotopy Types, Electronic Notes in Theoretical Computer Science 52 (2) 2002 (PS,PDF,BIB), Extended abstract of a talk given at GETCO 2001.

This presentation is the sequel of a paper published in the GETCO'00 proceedings where a research program to construct an appropriate algebraic setting for the study of deformations of higher dimensional automata was sketched. This paper focuses precisely on detailing some of its aspects. The main idea is that the category of homotopy types can be embedded in a new category of dihomotopy types, the embedding being realized by the globe functor. In this latter category, isomorphism classes of objects are exactly higher dimensional automata up to deformations leaving invariant their computer scientific properties as presence or not of deadlocks (or everything similar or related). Some hints to study the algebraic structure of dihomotopy types are given, in particular a rule to decide whether a statement/notion concerning dihomotopy types is or not the lifting of another statement/notion concerning homotopy types. This rule does not enable to guess what is the lifting of a given notion/statement, it only enables to make the verification, once the lifting has been found.

Flows over strict omega-groupoid

Philippe Gaucher. The branching nerve of HDA and the Kan condition (PS,PDF,BIB), Theory and Applications of Categories 11 n°3 (2003), p.75-106.

One can associate to any strict globular $\omega$-category three augmented simplicial nerves called the globular nerve, the branching and the merging semi-cubical nerves. If this strict globular $\omega$-category is freely generated by a precubical set, then the corresponding homology theories contain different informations about the geometry of the higher dimensional automaton modeled by the precubical set. Adding inverses in this $\omega$-category to any morphism of dimension greater than $2$ and with respect to any composition laws of dimension greater than $1$ does not change these homology theories. In such a framework, the globular nerve always satisfies the Kan condition. On the other hand, both branching and merging nerves never satisfy it, except in some very particular and uninteresting situations. In this paper, we introduce two new nerves (the branching and merging semi-globular nerves) satisfying the Kan condition and having conjecturally the same simplicial homology as the branching and merging semi-cubical nerves respectively in such framework. The latter conjecture is related to the thin elements conjecture already introduced in our previous papers.

Philippe Gaucher. About the globular homology of higher dimensional automata (DJVU,PDF,BIB), Cahiers de Topologie et Géométrie Différentielle Catégoriques, p.107-156, vol XLIII-2 (2002).

We introduce a new simplicial nerve of higher dimensional automata whose homology groups yield a new definition of the globular homology. With this new definition, the drawbacks noticed with the construction of Homotopy invariants of higher dimensional categories and concurrency in computer science disappear. Moreover the important morphisms which associate to every globe its corresponding branching area and merging area of execution paths become morphisms of simplicial sets.

Philippe Gaucher. Combinatorics of branchings in higher dimensional automata (PS,PDF,BIB), Theory and Applications of Categories 8 n°12 (2001), p.324-376.

We explore the combinatorial properties of the branching areas of execution paths in higher dimensional automata. Mathematically, this means that we investigate the combinatorics of the negative corner (or branching) homology of a globular $\omega$-category and the combinatorics of a new homology theory called the reduced branching homology. The latter is the homology of the quotient of the branching complex by the sub-complex generated by its thin elements. Conjecturally it coincides with the non reduced theory for higher dimensional automata, that is $\omega$-categories freely generated by precubical sets. As application, we calculate the branching homology of some $\omega$-categories and we give some invariance results for the reduced branching homology. We only treat the branching side. The merging side, that is the case of merging areas of execution paths is similar and can be easily deduced from the branching side.

Philippe Gaucher. From Concurrency to Algebraic Topology (PS,PDF,BIB), Electronic Notes in Theoretical Computer Science 39 (2000), no. 2, 19p. Extended abstract of a talk given at GETCO 2000

This paper is a survey of the new notions and results scattered in other papers. However some speculations are new. Starting from a formalization of higher dimensional automata (HDA) by strict globular $\omega$-categories, the construction of a diagram of simplicial sets over the three-object small category $-\leftarrow gl\rightarrow +$ is exposed. Some of the properties discovered so far on the corresponding simplicial homology theories are explained, in particular their links with geometric problems coming from concurrency theory in computer science.

Philippe Gaucher. Homotopy invariants of higher dimensional categories and concurrency in computer science (PS,PDF,BIB). Mathematical Structure in Computer Science 10 (2000), no. 4, p.481-524.

The strict globular $\omega$-categories formalize the execution paths of a parallel automaton and the homotopies between them. One associates to such (and any) $\omega$-category $\C$ three homology theories. The first one is called the globular homology. It contains the oriented loops of $\C$. The two other ones are called the negative (resp. positive ) corner homology. They contain in a certain manner the branching areas of execution paths or negative corners (resp. the merging areas of execution paths or positive corners) of $\C$. Two natural linear maps called the negative (resp. the positive ) Hurewicz morphism from the globular homology to the negative (resp. positive) corner homology are constructed. We explain the reason why these constructions allow the reinterpretation of some geometric problems coming from computer science.

Cyclic homology (in French)

Philippe Gaucher. Lambda-opérations sur l'homologie d'une algèbre de Lie de matrices (PS,BIB). K-Theory, vol. 13(2), p.151-167, 1998.

Philippe Gaucher. Lambda-opérations et homologie des matrices (PDF,BIB). C. R. Acad. Sci. Paris Sér. I Math., 313(10):663-666, 1991.

One extends Loday-Procesi lambda-operations from the cyclic homology of $A$ to the homology of the Lie algebra $\bf{gl}_{\infty}( A)$ using exterior powers of matrices. In this way, we obtain an interpretation of this lambda-operations, originally defined in combinatorial terms, in terms of matrix operations. One shows a formula giving their behavior with respect to the direct sum of matrices. It uses the coproduct and the structure of ring objet induced by the tensor product of matrices.

Philippe Gaucher. Produit tensoriel de matrices, homologie cyclique, homologie des algèbres de Lie. Ann. Inst. Fourier (Grenoble), vol. 44(2), p.413-431, 1994 (PDF,BIB).

Philippe Gaucher. Produit tensoriel de matrices et homologie cyclique (PDF,BIB). C. R. Acad. Sci. Paris Sér. I Math., 312(1):13-16, 1991.

If $A$ is an associative and commutative $\mathbb{Q}$-algebra with unit, the tensor product of matrices enables us to define on the homology of the Lie algebra $\bf{gl}_{\infty}( A)$ a product which give it with the usual sum a graded ring structure which is commutative. One gives an explicit formula for this product. After restriction to the primitive part, this product coincides with the Loday-Quillen's product on cyclic homology.

Site