Un mot pour l'audience: il n'y avait pas d'erreur dans le transparent page 24. Je sais précisément caractériser les équivalences faibles de la double localisation de Bousfield avec le foncteur L_O.

I will introduce the category of weak higher dimensional transition systems which contains the Cattani-Sassone ones as a small-orthogonality class. I will explain its categorical and homotopical properties, and the links with process algebras, bisimulation, and the topological models of concurrency.

Résumé (PS,PDF)

In directed algebraic topology, the concurrent execution of n actions is abstracted by a full n-cube. Each coordinate corresponds to one of the n actions. This n-cube may be viewed as a representable presheaf of the category of precubical sets, as a topological n-cube equipped with some continuous paths modelling the possible execution paths up to homotopy, and as a commuting n-cube, i.e usually the small category associated with the poset of vertices of the n-cube. In fact, we have to remove the identity maps for various reasons, e.g., because the full n-cube does not contain any loop. In this talk, all these points of view are related to one another by considering Milner's calculus of communicating systems (CCS). All operators of this process algebra are given a higher dimensional interpretation. The restriction to dimension 1 corresponds to the usual structural operational semantics.

There exist various methods for modeling time flows associated with concurrent systems. The study of the branching and merging homologies of a time flow requires a very specific feature: the mapping taking an object to its set of non-constant execution paths must be functorial. The first model I studied is the one of non-contracting Kan strict globular omega-categories consisting of the category of strict globular omega-categories C such that PC=C_1 U C_2 U ... is a strict omega-groupoid (hence the word ``Kan'', C_n being the set of n-morphisms) and of omega-functors f:C -> D inducing a map of strict omega-groupoids Pf:PC->PD (hence the word ``non-contracting''). The second model I studied is a version of the preceding model in which the path space PC is topologized, hence the notion of flows (small category without identities enriched over topological spaces). The third and last model I am studying now is a variant of M. Grandis' notion of d-space, the multipointed d-spaces, in which not only the path space is topologized, but also the direction of time. The three models are locally presentable, by working with Delta-generated spaces. The last one of multipointed d-spaces is also topological. In this talk, I will present the last model and its relation with the model of flows.

Je vais présenter une construction purement homotopique de l'espace des chemins et des homotopies de dimension supérieure des algèbres de processus (je me concentrerai sur CCS) : la restriction en dimension 1 redonnant la construction habituelle en terme de systèmes de transition étiquetés. Pour cela, je partirai d'une construction à valeur dans les ensembles précubiques (étiquetés), élaborée en partant d'une idée de K. Worytkiewitcz, mais un peu modifiée pour tenir compte du paradigme des automates de haute dimension : un et un seul n-cube plein pour l'exécution concurrente de n transitions. Puis en utilisant un foncteur réalisation des ensembles précubiques dans les flots (étiquetés), on verra comment les particularités algébriques et homotopiques de cette dernière catégorie permettent d'obtenir notamment une formalisation du produit parallèle avec synchonisation complètement débarassée de toute combinatoire, c'est-à-dire sans construction cosquelette, et en fait n'utilisant que des colimites homotopiques.

La dihomotopie (pour homotopie dirigée) est une équivalence entre flots temporels préservant la structure causale du flot et le type d'homotopie de l'espace d'états sous-jacent. La principale difficulté pour modéliser la dihomotopie est la contractibilité des chemins non bouclés et les définitions naïves qui préservent uniquement l'antériorité temporelle détruisent donc la structure causale. On introduit dans cet exposé les flots non-étiquetés et étiquetés, obtenant ainsi un modèle de parallélisme (contenant les automates de haute dimension, les algèbres de processus avec n'importe quelle algèbre de synchronisation, les systèmes de transitions asynchrones, les structures d'évènements etc...). Puis on introduit une catégorie de modèles dont les équivalences faibles sont les S-homotopies faibles. En Bousfield localisant par rapport à un ensemble de cofibrations modélisant le rafinement de l'observation, on obtient une catégorie de modèles dont les équivalences faibles sont appelées quasidihomotopie. La dihomotopie est entre la S-homotopie et la quasidihomotopie. Cette dernière est comme la dihomotopie sauf dans des parties non-observables du flot temporel. Les objets locaux sont notamment les flots avec les parties non-observables remplies. Je présenterai des problèmes ouverts et quelques résultats, notamment concernant des invariants détectant les zones de branchements ou de confluences non-déterministes, et les relations entre la dihomotopie et la quasidihomotopie. Si le temps le permet, je parlerai d'une autre approche de la dihomotopie des flots utilisant des flots de Segal (i.e. des flots faibles) et des catégories de modèles de Rezk. Cette approche encore très expérimentale est nécessaire pour de futurs développements homologiques.

Dihomotopy (for directed homotopy) is an equivalence between time flows preserving the causal structure and the homotopy type of the underlying state space. The main difficulty to model dihomotopy is that non-looped continuous paths are contractible. Therefore the naive definitions preserving only the order of time fail to preserving the causal structure. In this talk, I introduce the unlabeled and labeled flows, obtaining this way models for concurrency (containing higher dimensional automata, process algebras with any synchronization algebra, asynchronous transition systems, event structures etc...). I then introduce a model category structure whose weak equivalences are called S-homotopy. By Bousfield localizing with respect to a set of cofibrations modeling refinement of observation, one obtains a new model category whose weak equivalences are called quasidihomotopy. Dihomotopy is between S-homotopy and quasidihomotopy. Quasidihomotopy is like dihomotopy except in non-observable areas of the time flow. In particular, local objects are flows with all non-observable areas filled. Open problems and a few results will be presented, concerning some invariants detecting the non-deterministic branching and merging areas and the relation between dihomotopy and quasidihomotopy. If the time permits, another approach of dihomotopy using Segal flows (i.e. weak flows) and Rezk model category structures will be presented. The latter approach is very experimental but it is needed for future homological developments.

Globular complexes and flows are designed to modelling spatial and temporal deformations of higher dimensional automata, modelling this way the invariance of the time flow of a HDA by subdivision and refinement of observation. A HDA is modelled in the framework of flows by a set of states (the 0-skeleton) and between each pair (a,b) of states by a topological space whose elements play the role of the execution paths from a to b. These data are equipped with an associative composition law which plays the role of composition of execution paths. Spatial deformations (S-homotopy) are very well interpreted by a Quillen model category structure on the category of flows. Temporal deformations (T-homotopy) are considerably more difficult to model and to understand. A convincing formalization will be proposed which will make use of the preceding model category structure. It will be explained why the underlying space of the time flow (defined only up to homotopy) is preserved and why the topological configurations of branching and merging areas of execution paths of the time flow are also preserved.

An application of the preceding constructions will be proposed : an analogue of Whitehead's theorem for the full dihomotopy relation, and not only for S-homotopy as in previous works of the author, will be presented. This theorem says that a morphism between cofibrant homotopy continuous flows is a weak dihomotopy equivalence if and only if it is invertible up to dihomotopy and that every flow is weakly dihomotopy equivalent to a cofibrant homotopy continuous flow. This cofibrant homotopy continuous representative is of course unique up to dihomotopy. This first structural theorem for the full dihomotopy relation of Flow proves at least one thing : dihomotopy is really a new kind of homotopy.

We give an overlook of our work about globular complexes and flows. Globular complexes, flows, S-homotopy and T-homotopy are explained by examples. Several model categories are presented. And some open questions are discussed.

Les flots sont un modèle de parallélisme permettant de définir une notion de dihomotopie sans utiliser un choix non-canonique de pointage des états. La dihomotopie des flots contient la S-homotopie qui commence à être bien comprise et qui donne déjà quelques résultats (par exemple une longue suite exacte pour les branchements et les confluences en haute dimension), et la T-homotopie . Après avoir défini cette dernière, j'expliquerai pourquoi toute structure modèle sur les flots ou bien n'a pas assez d'équivalences faibles, ou bien a trop d'équivalences faibles, les équivalences faibles en trop étant des morphismes qui modifient ou bien l'homologie des branchements, ou bien l'homologie des confluences. Et comment cela m'a donné l'idée d'introduire une catégorie de préfaisceaux sur une petite sous-catégorie des flots. Puis en admettant le principe de Vopenka, j'expliquerai pourquoi aucune des structures modèles connues (ou du moins que je connais) ni aucune de leur localisation homotopique ne convient pour l'étude de la T-homotopie sur cette catégorie de préfaisceaux car toutes ont, encore, des équivalences faibles parasites qui modifient l'homologie des branchements ou des confluences. En conclusion, je ne répondrai probablement pas à la question posée mais je donnerai au cours de l'exposé les arguments mi-géométriques mi-catégories de modèles qui me font penser qu'une telle catégorie de modèles existe.

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.

On explique dans ces transparents les trois structures de catégorie modèle trouvées jusqu'ici sur la catégorie des flots.

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.