Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1. We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. We construct a word x such that the symbol at position n is equal to the symbol at position 2n. Thus, x is the join of x itself and the subsequence of odd positions of x. We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.
This is joint work with Olivier Carton (Universitéé Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).[-]

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.[-]

The study of palindromes and their generalizations in a word has gained a lot of interest in the last 20 years, motivated by applications in physics, biology, discrete geometry, to name only a few. Using Sebastien Ferenczi as an example, we illustrate the computation of its palindromic complexity and its relation with the usual factor complexity, via an identity attributed to Brlek and Reutenauer involving also the palindromic defect. Periodic infinite words as well as the family of words with language closed by reversal also satisfy the identity. The identity remains valid when palindromic is replaced by $\sigma$-palindromic, and we also discuss some other patterns.[-]

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.[-]

In the way of Arnoux-Ito, we give a general geometric criterion for a subshift to be measurably conjugated to a domain exchange and to a translation on a torus. For a subshift coming from an unit Pisot irreducible substitution, we will see that it becomes a simple topological criterion. More precisely, we define a topology on $\mathbb{Z}^d$ for which the subshift has pure discrete spectrum if and only if there exists a domain of the domain exchange on the discrete line that has non-empty interior. We will see how we can compute exactly such interior using regular languages. This gives a way to decide the Pisot conjecture for any example of unit Pisot irreducible substitution.
Joint work with Shigeki Akiyama.[-]

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.[-]

We introduce a family of block-additive automatic sequences, that are obtained by allocating a weight to each couple of digits, and defining the nth term of the sequence as being the total weight of the integer n written in base k. Under an additional combinatorial difference condition on the weight function, these sequences can be interpreted as generalised Rudin–Shapiro sequences. We prove that these sequences have the same two-term correlations as sequences of symbols chosen uniformly and independently at random. The speed of convergence is independent of the prime factor decomposition of k. This extends work by E. Grant, J. Shallit, T. Stoll, and by P.-A. Tahay.[-]

We show how to construct 'simple' symbolic dynamical systems in terms of renormalisation schemes associated with multidimensional continued fractions. Continued fractions are used here to generate infinite words thanks to the iteration of infinite sequences of substitutions. Simple means that these symbolic systems have a linear number of factors of a given length, or that they have pure discrete spectrum, or else, that they have a low symbolic discrepancy. We also discuss the relation between these notions.[-]

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.[-]