We consider the problem of deciding termination of linear constraint loops, that is, single-path loops in which the loop body consists of a (possibly non-deterministic) assignment, specified a conjunction of linear constraints. We present several versions of this problem, according to the syntactic form of the loop and the numerical domain of the program variables. We sketch some decidability results and point out open problems.

We consider extensions of monadic second order logic over $\omega$-words, which are obtained by adding one language that is not $\omega$-regular. We show that if the added language $L$ has a neutral letter, then the resulting logic is necessarily undecidable. A corollary is that the $\omega$-regular languages are the only decidable Boolean-closed full trio over $\omega$-words.

(Joint work with Mikołaj Bojańczyk, Edon Kelmendi, and Rafał Stefański)

Dans les années 1970, William Tutte développa une approche algébrique, basée sur des « invariants », pour résoudre une équation fonctionnelle qui apparait dans le dénombrement de triangulations colorées. La transformée de Laplace de la distribution stationnaire du mouvement brownien réfléchi dans des cônes satisfait une équation similaire. Pour être applicable, cette méthode requiert l’existence de deux fonctions appelées respectivement invariant et fonction de découplage. Tous les modèles ont des invariants mais on démontre que l’existence de fonctions de découplage équivaut à une condition géométrique simple sur les angles de réflexion. Pour les modèles qui ont une fonction de découplage, on obtient une expression explicite sans intégrale de la transformée de Laplace en fonction des invariants. En particulier, on obtient à nouveau une formule pour la transformée de Laplace de plusieurs cas bien connus, comme la skew symétrie, les réflexions orthogonales ou le résultat de Dieker et Moriarty qui caractérise les densités stationnaires qui s’écrivent sous la forme d’une somme d’exponentielles. Cette méthode permet de plus de caractériser la nature algébrique de la transformée de Laplace en fonction des modèles. Cet exposé est issu d’un travail en collaboration avec M. Bousquet-Mélou, A. Elvey Price, C. Hardouin et K. Raschel.

The notion of operadic category appeared in the work of Batanin and Markl as a tool for working with various operad like structures. Each operadic category O has an associated category of O-operads with values in an arbitrary symmetric monoidal category. Operadic categories and operadic functors form a category.

In my talk I will show that the category of symmetric operads in Set (variation of colours is allowed) is a reflective subcategory of the category of operadic categories. The inclusion is given by (operadic) Grothendieck construction and the reflection is given by evaluation of the left Kan extension along arity functor on the terminal operad. Thus the notion of operadic category can be considered as a flexible extension of the notion of symmetric operad.

Moreover, there is yet another functor from operadic categories to symmetric operads which sends an operadic category O to a symmetric operad in Set whose algebras are exactly O-operads. These three functors (Grothendieck construction, its left adjoint and free operad functor) fit in a nice picture with a universal property. In particular, they various composites generate the Baez-Dolan +-constructions for both symmetric operads and operadic categories.

Categorical abstraction is a powerful organizing principle in computer algebra. In this talk, we explain the concept of constructive category theory and how we implement this concept in our software project CAP-Categories, algorithms, programming. In CAP it is possible to implement higher algorithms and data structures using basic categorical operations as primitives, which in turn often rely on classical algorithms in computer algebra like the computation of Gröbner bases. As an example, we show how our categorical framework can be used for computing with finitely presented functors.

In this talk, we consider multiplayer games on graphs. In such games, each player has his own objective, that does not necessarily clash with the objectives of the other players. In this “non zero-sum” context, equilibria are a better suited solution concept than the classical winning strategy notion. We will focus on a refinement of the well-known Nash Equilibrium concept: Subgame Perfect Equilibrium (SPE for short), where players have to play rationnally in every scenario, even the ones that deviate from the planned outcome. We will explain why this refinement is a relevant solution concept in multiplayer games and show how to handle them in quantitative reachability games, where each player wants to minimize the number of steps to reach its own target set of vertices.