Homotopy in Concurrency and Rewriting

Bâtiment Turing

The conference will take place from 9 to 12 June 2015 in École Polytechnique (in Turing building, room Gilles Kahn).


This conference on directed algebraic topology, concurrency and rewriting aims at bringing together researchers interested in applying methods originating in topology and in higher-dimensional rewriting. It is motivated by the discovery, over the recent years, of many connections between the study of concurrent processes from a topological point of view and rewriting methods and structures. It will be interested in applications of those fields to problems commonly encountered in computer science, in the study of concurrent and distributed processes, in semantics of programming languages, but also to more theoretical questions arising from the study of structures found in algebraic topology such as operads and higher-dimensional categories.

On the one hand, there has been an increasing interest in the potential applications of algebraic topology to study concurrency over the past decades. This new field at the intersection of topology and computer science was started by a series of works which introduced semantics of concurrent programs based on topological spaces, whose points model the states of programs and paths model executions of the program. Since executions of programs always go forward in time, these topological spaces should be equipped with a notion of direction for paths, which requires adapting the usual tools in algebraic topology to this new setting. Two paths which are homotopic (in a directed sense) correspond to two schedulings of a concurrent program which are equivalent in the sense that they give rise to the same results. Starting from this observation, the study of the space of paths up to homotopy in a directed space provides compact representations of the possible schedulings of concurrent programs, in the same way that homotopy (or homology) groups describe in a concise way the essential characteristics of classical topological spaces. This point of view has provided new tools in order to efficiently verify concurrent programs by providing compressed representations of their state space, and open new research fields such as the investigations of variants of homology adapted to the directed setting. Another major application of algebraic topology in the study of concurrent programs can be found in the classification of tasks which can be performed by asynchronous concurrent programs, by modeling coherent states of threads using simplicial complexes and drawing conclusions from the study of their geometrical properties.

On the other hand, directed methods appear also in homological algebra throughout rewriting. Since the eighties, several results (Anick, Squier, Kobayashi, Brown, etc.) have shown the interest of methods coming from rewriting theory to compute homological invariants (resolutions, homology groups, Hilbert and Poincaré series). Moreover, convergent (confluent and terminating) presentations, and Gröbner bases for linear structures, allow the computation of normal forms and thus, one can address decision problems (Dehn’s problems, combinatorics of Coxeter and Artin groups) through computational methods. Recently, these rewriting methods have been generalized from strings to richer algebraic structures such as operads, monoidal categories, and more generally higher-dimensional categories. These extensions of rewriting fit in the general scope of higher-dimensional rewriting theory, which has emerged as a unifying algebraic framework. This approach allows one to perform homotopical and homological analysis of rewriting systems (Squier theory). It also provides new computational methods in combinatorial algebra (Artin-Tits monoids, Coxeter and Garside structures), in homotopical and homological algebra (construction of cofibrant replacements, Koszulness properties).

Overall, the conference will cover the following topics:


Tuesday 9 June

9:30Sanjeevi KrishnanPositive Alexander Duality
11:00Steve OudotReflections in quiver and persistence theories
14:00Carlos SimpsonA two-dimensional generalization of Stallings core graphsarticlevideo
15:30Marcelo FioreAlgebraic Theories for Type and Homotopy Theories

Wednesday 10 June

9:30Vladimir DotsenkoAssociahedra and noncommutative topological field theory
11:00Timothy PorterSteps towards a "directed homotopy hypothesis"slides
14:00Emily BurgunderFree algebraic structures on the permutehedraarticle
15:30Richard SteinerChain complexes and higher categoriesslides

Thursday 11 June

9:30Jérémy DubutNatural Homology
11:00Dimitri AraA Quillen's Theorem A for strict ∞-categories
14:00Viktoriya OzornovaFactorability structureslides
15:30Albert BurroniMachines et grammaires polygraphiques

Friday 12 June: CATHRE ANR meeting

On Friday will take place the meeting of the CATHRE ANR project.

9:30Eric HoffbeckEnsembles dendroïdaux et produit shuffle
11:00Stéphane Gaussent Réécrire les chemins de Littelmann
14:00Yves LafontCalcul oriental
15:30Jovana ObradovićOn the various definitions of cyclic operads
16:30Clément AlleaumeRéécriture dans les catégories monoïdales linéaires


Dimitri Ara (Institut de mathématiques de Marseille) — A Quillen's Theorem A for strict ∞-categories

Quillen's Theorem A is one of the main tool in the study of homotopy types of categories. It gives a sufficient condition on a functor for its nerve to be a weak homotopy equivalence of simplicial sets. In this talk, I will explain how to generalize Quillen's Theorem A to strict ∞-categories using Street's nerve. The proof involves various tools interesting in their own right such as a join construction, generalized slices and a connection between lax transformations and simplicial homotopies. An essential tool to obtain these results is Steiner's theory of augmented directed complexes. This is joint work with G. Maltsiniotis.

Albert Burroni — Machines et grammaires polygraphiques

A l'instar des systèmes de réécriture de mots qui sont des présentations de monoïdes, les polygraphes sont des présentations de catégories en dimensions supérieures (autrement dit, ce sont des systèmes de réécriture en dimensions supérieures). Ces polygraphes, complétés en logographes (i.e. munis de systèmes d'entrées et de sorties) deviennent des automates qui permettent la reconnaissance de langages en dimensions supérieures. Nous illustrerons cela avec des langages d'images qui sont formés de mots de dimension 2.

Emily Burgunder (Institut Mathématiques Toulouse) — Free algebraic structures on the permutehedra

Tridendriform algebras are a type of associative algebras, introduced independently by Chapoton and by Loday-Ronco, in order to describe operads related to the Stasheff polytopes. The vector space ST spanned by the surjections from {1,...n} to {1,...,r}, which describes the faces of permutohedra, has a natural structure of tridendriform bialgebra. We prove that it is free as a tridendriform algebra and exhibit a basis.

This is joint work with Pierre-Louis Curien and Maria Ronco.

Vladimir Dotsenko — Associahedra and noncommutative topological field theory

I shall explain how toric varieties of (Loday's realisations of) associahedra give rise to a new remarkable algebraic structure that is in many ways a noncommutative counterpart of the notion of genus 0 cohomological field theory. This is a joint work with Sergey Shadrin and Bruno Vallette.

Jérémy Dubut (ENS Cachan) — Natural Homology

We propose a notion of homology for directed algebraic topology, based on so-called natural systems of abelian groups, and which we call natural homology. Contrary to previous proposals, and as we show, natural homology has many desirable properties:

Marcelo Fiore — Algebraic Theories for Type and Homotopy Theories

I will first present foundations for (untyped and simply typed) algebraic theories with variable-binding operators, addressing the mathematical theory from the viewpoints of universal algebra, equational logic, and categorical algebra. In an exploratory vein, I will subsequently pursue the perspective provided by this model theory in the context of homotopy theory, introducing an abstract categorical framework for uniform Kan-like filler algebraic structure and discussing its intended applications.

Sanjeevi Krishnan — Positive Alexander Duality

The real homology groups of a directed space naturally come equipped with cones, as constructed by Grandis, encoding some of the directionality of the space. Alexander Duality is a duality between the homology of a space and the cohomology of its complement in a sphere. We accordingly construct positive cones on the real cohomology of certain directed spaces, sufficiently smooth spaces parametrized over the real number line, and give a positive Alexander Duality in homological degrees 0,1. Positive cohomology, the limit of a sheaf of local positive cohomology semigroups on the real number line, can be computed as a linear programming problem. A natural application of this Positive Alexander Duality is to characterize when an evader can avoid capture in certain pursuit-evasion games. After describing this application, we briefly outline possible other applications (like concurrency) that should fall out of suitable generalizations from the case presented here. This is joint work with Rob Ghrist.

Yves Lafont — Calcul oriental

L'« oriental de dimension n » est le simplexe de dimension n muni d'une structure de n-catégorie (stricte). Il est donc « orienté » en un sens assez fort : son bord est ainsi formé d’une « source » et d’un « but » composés eux-mêmes de simplexes de dimensions inférieures. Les orientaux permettent en particulier de définir le « nerf » d’une catégorie de dimension supérieure, et donc son homologie. Cette notion a été introduite par Ross Street en 1987, mais son article est particulièrement ardu. Albert Burroni a proposé une construction plus simple, en itérant un foncteur « expansion », qui transforme toute n-catégorie en une n+1-catégorie, en lui ajoutant une « origine ». Or ce foncteur est une monade, ce qui donne un plongement de la catégorie simpliciale (augmentée) dans celle des catégories de dimension supérieure, dont on peut déduire le foncteur nerf. Après avoir défini les notions de « cylindre », de « cône », et d’expansion, je dévoilerai le calcul qui permet de faire cette construction explicitement.

Steve Oudot (INRIA Saclay) — Reflections in quiver and persistence theories

Reflections are among the classical operations used in quiver theory to transform a given quiver Q into another quiver Q'. The nice feature of such a reflection is to be associated with a functor mapping the representations of Q into representations of Q'. This is interesting in the context of the classification of quiver representations, where decompositions of representations of Q can be transferred to decompositions of representations of Q'. This principle has been applied with success by Bernstein, Gelfand and Ponomarev to prove Gabriel's theorem and some of its extensions in the 70's and 80's. In this talk I will draw a connection between reflection functors and the Diamond Principle from persistence theory, then I will present an application to the computation of persistence for so-called zigzags.

Viktoriya Ozornova — Factorability structure

This is a joint work with A. Heß. A factorability structure on a group or a monoid is a choice of geodesic normal forms with respect to a fixed generating system with certain compatibility properties. Factorability structure yields a smaller chain complex than the bar complex for computing the homology of the given monoid or group. Moreover, under some additional assumptions, factorability yields a complete string rewriting system on the monoid. Examples of factorability structures can be found on symmetric groups, braid groups (and more general, Garside groups), and on arbitrary Artin monoids.

Tim Porter (University of Bangor) — Steps towards a "directed homotopy hypothesis": (∞,1)-categories, directed spaces and rewriting: An overview of some techniques and some questions

It is now almost "classical" that ∞-groupoids correspond to "spaces" and encode certain aspects of "rewriting" for (low dimensional) categories. We will review some of the models for this. It has more recently been suggested that (∞,1)-categories might correspond in a similar way to directed spaces. We will examine various aspects hopefully looking at the same time for any means of applying insights from this study to rewriting.

Carlos Simpson — A two-dimensional generalization of Stallings core graphs

Two-dimensional constructions, glued from polyhedra modeled on the affine Weyl chambers for SL3, are the structures forming pieces of two dimensional euclidean Bruhat-Tits buildings. In joint work with Katzarkov, Noll and Pandit, we propose a combinatorial reduction process starting from such a construction but with positively curved points, going towards a negatively curved "pre-building". An important role is played by a subcomplex homeomorphic to a Riemann surface, which appears to be analogous to the Stallings core graph as studied by Parzanchevski, Puder and others in similar one-dimensional reduction processes.

Richard Steiner (University of Glasgow) — Chain complexes and higher categories

It is well known that there is an equivalence from the category of chain complexes to the category of ω-category objects in the category of abelian groups, where an ω-category is a particular type of higher category. I will define a category of augmented directed chain complexes in which the objects are chain complexes with additional structure and the morphisms are structure-preserving chain maps. By modifying the equivalence one obtains a functor from augmented directed complexes to ordinary ω-categories (that is, ω-category objects in the category of sets). In turn, this functor restricts to an equivalence between two important full subcategories, yielding an algebraic description of certain important ω-categories. These ω-categories include the simple ω-categories (associated to globes and finite discs) and Street's orientals (associated to simplexes). They also include the ω-categories associated to cubes and (with some adjustments) the ω-categories associated to opetopes. One can obtain alternative descriptions of the class of ω-categories: they are equivalent to simplicial sets with additional structure (complicial sets) and to cubical sets with additional structure (cubical sets with compositions and connections).

Practical information

The conference will take place in bâtiment Turing at École Polytechnique, in room Gilles Kahn. You can find instructions about how to get there.


For any practical or theoretical matter, you can contact Samuel Mimram (local organizer à École Polytechnique), Yves Guiraud ou Philippe Malbos.


The meeting is supported by ACAT ESF networking programme and CATHRE ANR project.