Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given finitely presented group $0$, is there an algorithm that determines if the group $G$ is tilable with a finite set of tiles? In this lecture I will start with a presentation of two different proofs of the undecidability of the domino problem on $Z^2$. Then we will discuss the case of finitely generated groups. Finally, the emptiness problem for general subshifts will be tackled.[-]

The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its applications to $b$-automatic sequences. Then I will move to $b$-regular sequences, which can be viewed as a generalization of $b$-automatic sequences to integer-valued sequences. I will explain bow first-order logic can be used to show that many enumeration problems of $b$-automatic sequences give rise to corresponding $b$-regular sequences. Finally, I will consider more general frameworks than integer bases and (try to) give a state of the art of the research in this domain.[-]

Les Acides RiboNucléiques (ARN) sont des biopolymères linéaires omniprésents dans notre organisme, pouvant être codés comme des séquences sur un alphabet A,C,G,U. Ces molécules se replient sur elles-mêmes, établissant des liaisons hydrogènes d'où découlent l'appariement de certaines des positions, selon des règles de compatibilité des lettres n'autorisant que les paires dans l'ensemble A,U,C,G,G,U. De ce mécanisme d'appariements résulte l'adoption d'une ou plusieurs conformations, appelées structures secondaires, au passage bijectif avec les mots de Motzkin sans-pic. De nombreuses applications, en nanotechnologie, médecine, ou biostatistique, nécessitent de compter, ou encore engendrer aléatoirement, des séquences d'ARN simultanément compatibles avec un ensemble donné de structures secondaires. Un algorithme exponentiel, basé sur une décomposition (ear decomposition) du graphe de dépendance induit par l'union des paires, a ainsi été proposé par Höner zu Siederdissen et al [A]. Cet algorithme utilise la méthode récursive/programmation dynamique pour précalculer les nombres d'affectations compatibles avant/après chacun des choix locaux. Une phase de génération utilise ensuite ces nombres pour garantir l'uniformité de la génération. Cependant, cet algorithme ne permettait pas la prise en compte de critères énergétiques plus complexes, nécessitant l'utilisation d'un formalisme plus expressif que les graphes de dépendance (hypergraphes). De plus, la complexité de l'algorithme, théoriquement exponentielle sur un paramètre non-borné et parfois élevée en pratique, soulevait la question de la complexité du problème de comptage.
Dans un travail récent avec Hammer, Wang et Will [B], nous établissons la #P complétude, et la complexité d'approximation, du problème de comptage des séquences compatibles. Notre preuve repose sur une bijection simple entre les séquences compatibles et les stables du graphes de dépendance. Nous proposons une approche alternative, basée sur la décomposition arborescente, pour contrôler de façon probabiliste [C] l'énergie moyenne des séquences pour les différentes structures, ou la composition en les différentes lettres. Ces résultats fournissent un cadre flexible et expressif pour le design d'ARN, et soulèvent des questions sur l'utilisation de stratégies alternatives (génération de Boltzmann, simulation parfaite) pour la génération aléatoire, ainsi sur le concept d'analyse en moyenne dans un contexte où la donnée en entrée est plus complexe que la taille de l'objet engendré.[-]

Two-player turn-based zero-sum games on (finite or infinite) graphs are a central framework in theoretical computer science — notably as a tool for controller synthesis, but also due to their connection with logic and automata theory. A crucial challenge in the field is to understand how complex strategies need to be to play optimally, given a type of game and a winning objective. I will give a tour of recent advances aiming to characterize games where finite-memory strategies suffice (i.e., using a limited amount of information about the past). We mostly focus on so-called chromatic memory, which is limited to using colors — the basic building blocks of objectives — seen along a play to update itself. Chromatic memory has the advantage of being usable in different game graphs, and the corresponding class of strategies turns out to be of great interest to both the practical and the theoretical sides.[-]

Rivin conjectured that the conjugacy growth series of a hyperbolic group is rational if and only if the group is virtually cyclic. In this talk I will present the proof (joint with Hermiller, Holt and Rees) that the conjugacy growth series of a virtually cyclic group is rational, and then also confirm the other direction of the conjecture, by showing that the conjugacy growth series of a non-elementary hyperbolic group is transcendental (joint with Antolín). The result for non-elementary hyperbolic groups can be used to prove a formal language version of Rivin's conjecture for any finitely generated acylindrically hyperbolic group G, namely that no set of minimal length conjugacy representatives of G can be regular.[-]

Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.

First, we look at minimal and maximal complexity. Studying minimal complexity leads to results on ultimately periodic and Sturmian words, similar to the results by Morse and Hedlund on the usual factor complexity. Maximal complexity is related to counting the number of equivalence classes. As a more complicated topic, we study the question of how much k-abelian complexity can fluctuate between fast growing and slowly growing values. These questions could naturally be asked also in a setting where we restrict our attention to some subclass of all words, like morphic words.[-]

The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.
In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff's game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review some of their characterizations (in terms of morphisms, finiteness of their k-kernel,...). These sequences take values in a finite set but the Sprague-Grundy function of a game, such as Nim of Wythoff, is usually unbounded. This provides a motivation to introduce k-regular sequences (in the sense of Allouche and Shallit) whose k-kernel is not finite, but finitely generated.
In the second lecture, games played on several piles of token naturally give rise to a multi-dimensional setting. Thus, we reconsider k-automatic and k-regular sequences in this extended framework. In particular, determining the structure of the bidimensional array encoding the (loosing) P-positions of the Wythoff's game is a long-standing and challenging problem in CGT. Wythoff's game is linked to non-standard numeration system: P-positions can be determined by writing those in the Fibonacci system. Next, we present the concept of shape-symmetric morphism: instead of iterating a morphism where images of letters are (hyper-)cubes of a fixed length k, one can generalize the procedure to images of various parallelepipedic shape. The shape-symmetry condition introduced twenty years ago by Maes permits to have well-defined fixed point.
In the last lecture, we move to generalized numeration systems: abstract numeration systems (built on a regular language) and link them to morphic (multidimensional) words. In particular, pictures obtained by shape-symmetric morphisms coincide with automatic sequences associated with an abstract numeration system. We conclude these lectures with some work in progress about games with a finite rule-set. This permits us to discuss a bit Presburger definable sets.[-]

Dimension groups are invariants of orbital equivalence. We show in this lecture how to compute the dimension group of tree subshifts. Tree subshifts are defined in terms of extension graphs that describe the left and right extensions of factors of their languages: the extension graphs are trees. This class of subshifts includes classical families such as Sturmian, Arnoux-Rauzy subshifts, or else, codings of interval exchanges. We rely on return word properties for tree subshifts: every finite word in the language of a tree word admits exactly d return words, where d is the cardinality of the alphabet.
This is joint work with P. Cecchi, F. Dolce, F. Durand, J. Leroy, D. Perrin, S. Petite.[-]

Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for participants to get some hands-on training on how to use Walnut.[-]