Orateur : Aldo Gonzales-Lorenzo (post-doc LIRIS)
Titre : Homologie algorithmique pour les objets discrets
Résumé : La théorie de l’homologie formalise la notion de trou dans un espace. Pour un sous-ensemble de l’espace Euclidien, on définit une séquence de groupes d’homologie, dont leurs rangs sont interprétés comme le nombre de trous de chaque dimension. Ainsi, β0 (le rang du groupe d’homologie de dimension zéro) est le nombre de composantes connexes, β1 est le nombre de tunnels ou anses et β2 est le nombre de cavités. Ces groupes sont calculables quand l’espace est décrit d’une façon combinatoire, comme c’est le cas pour les complexes simpliciaux ou cubiques. À partir d’un objet discret (un ensemble de pixels, voxels ou leur analogue en dimension supérieure) nous pouvons construire un complexe cubique et donc calculer ses groupes d’homologie.
Dans cette présentation je parlerai de deux approches relatives au calcul de l’homologie sur des objets discrets. Primo, je présenterai le champ de vecteurs discret homologique, une structure combinatoire qui permet de calculer les groupes d’homologie. Secundo, je présenterai deux mesures (l’épaisseur et la largeur) associées aux trous d’un objet discret, ce qui permet d’obtenir une signature topologique et géométrique plus intéressante que les simples nombres de Betti.
Orateur : Damien Imbs (LIS AMU, new MCF)
Titre : Topological and algorithmic tools for computability in distributed computing
Résumé : One of the major breakthroughs in distributed computing was the discovery of its links with algebraic topology. This result earned its authors the Gödel prize in 2004. Topological tools are especially useful to prove impossibility results.
In this talk, I will present such topological tools and how to use them to prove the impossibility of distributed problems. In particular, I will show how to use Sperner’s Lemma to prove the impossibility of Set Agreement, a fundamental distributed problem, in a specific model. I will then present algorithmic techniques to extend this result to various distributed models of computation.
Orateur : Jeremie Chalopin (LIS AMU)
Titre : Un contre-exemple à la conjecture de Thiagarajan sur les structures d’évènements régulières
Résumé : On présente un contre-exemple à la conjecture de Thiagarajan (1996 et 2002) affirmant que les structures d’évènements régulières correspondent exactement à celles obtenues comme dépliages des réseaux de Petri 1-safe finis. Les structures d’évènements, les automates de trace sont des modèles fondamentaux pour la théorie de la concurrence. Il existe des interprétations élégantes de ces structures comme des objets combinatoires et géométriques, et on peut reformuler la conjecture dans ce cadre. Plus précisément, les domaines des structures d’évènements correspondent exactement aux graphes médians pointés et aux complexes cubiques CAT(0) pointés. Une condition nécessaire pour que la conjecture de Thiagarajan soit vérifiée est que les domaines des structures d’évènements régulières admettent un joli étiquetage régulier (regular nice labelling). Pour réfuter cette conjecture, on décrit le domaine d’une structure d’évènement régulière qui n’admet pas de tel étiquetage. Notre contre-exemple est basé sur une construction de Wise (1996 et 2007) d’un complexe de carrés de courbure non-positive dont le revêtement universel est un complexe de carrés CAT(0) contenant un plan muni d’un pavage apériodique.