Exposés Invités

Marie-Pierre Béal : Substitution shifts in dimension one

Résumé : We consider substitution shifts in dimension one. They are defined as the set $X(\sigma)$ of bi-infinite sequences of symbols in a finite alphabet $A$ whose finite factors are factors some $\sigma^n(a)$ for $a$ in $A$, where $\sigma$ is morphism from $A^*$ to $A^*$.

We show that a morphism $\sigma$ is recognizable on $X(\sigma)$ for aperiodic points. This property means that each aperiodic point has, up to some short shift, at most one pre-image by $\sigma$ in $X(\sigma)$. This result was proved by Mossé for primitive morphisms, by Bezugly et al. for aperiodic non-erasing morphisms, and by Berthé et al. for non-erasing morphisms.
We give an efficient algorithm to check whether an injective morphism is recognizable on $A^\Z$ for aperiodic points. We consider several decidable properties of substitution shifts in dimension one: deciding whether a word belongs to the set of finite factors of $X(\sigma)$, deciding whether a morphism is recognizable on $X(\sigma)$ for all points, deciding whether a substitution shift is minimal, deciding whether a substitution shift is irreducible, computing the points of $X(\sigma)$ containing only non-growing letters. We will finish with some open problems on decidable or undecidable properties of substitution shifts in dimension one.

This is a joint work with Dominique Perrin and Antonio Restivo.

Emmanuel Jeandel : Props and Symbolic Dynamics

Résumé : Props is a concept coming from the Lawvere school of category theory, and represents structures with two compositional laws: sequential and parallel composition. Examples abond in mathematics (functions with the usual composition and the cartesian product, matrices with matrix product and kronecker product...) and in computer science (boolean circuits). They are well suited for a purely combinatorial approach, and one can speak of props given by generators and relations. While group combinatorics is linked to word combinatorics (an element of a finitely presented group is a product of generators, hence for all intent and purposes a 1 dimensional word), props are usually represented by 2 dimensional objects (due to the fact we have two compositions) and one usually reason graphically about these objects. In this talk, I will explain this concept, and show how it can be used in symbolic dynamics for two relevant applications: to represent in a very nice way reversible Turing machines (more precisely generalized shifts), and how it can used to produce a purely categorical version of a well known problem in symbolic dynamics, the conjugacy problem. Category theory is sometimes seen as an exercise in notation, but we will see that it is not the case here : This rephrasing will give us a systematic way to uild new invariants (and recover ALL existing ones) in symbolic dynamics from some structures that are very well known and used in enumerative combinatorics, namely Hopf algebras.

Samuel Petite : Sous-shifts aux langages stables.

Résumé : Les sous-shifts aux langages stables  forment une classe de sous-shifts qui a été récemment introduite par V. Cyr et B. Kra. Cette famille contient de nombreux exemples classiques de sous-shifts, de diverses complexités allant des systèmes d’entropie strictement positive, comme les sous-shifts de type fini, aux systèmes de faible complexité, comme les sous-shifts de complexité linéaire. Ils sont génériques parmi la famille des sous-shifts. Nous présentons dans cet exposé quelques unes de leurs propriétés, notamment celles concernant leurs d’automorphismes.

Matthieu Rosenfeld : A simple counting argument

Résumé : We say that a word w is a square if w=uu for some non-empty word u. We say that a word is square-free if none of its factors is a square. Let S(n) be the set of square-free words of length n over the alphabet {0,1,2,3}. I will start my presentation with a simple proof that S(n) is non empty for any n. In fact, the idea of the proof is to show a stronger statement, that is, for all n>0, S(n+1)>2 S(n). Having a strong enough hypothesis is key since the proof proceeds by induction. The main interest of this result is the simplicity of the proof and the fact that the idea behind it is generalizable to many other problems.

I will then present other applications of the same idea to more difficult questions (from combinatorics on words, tilings, and graph theory) and I will discuss the links between this approach and other techniques such as:
- Kolpakov and Shur's method to count the number of repetition-free words;
- the power series method for combinatorics on words;
- the Lovasz Local Lemma and the entropy compression method.