Logo

Schedule

The meeting starts Monday 21st May at 9 a.m. and ends on Friday 25th May at 3 p.m.

printer friendly schedule

Monday, 21st May
9.00-10.00 D. Perrin, Invited lecture (1)
10.00-10.30 Coffee Break
10.30-11.30 M. Crochemore, Invited lecture (1)
11.30-12.30 N. Rampersad, Invited lecture (1)
12.30-15.30 Lunch/Break
15.30-16.30 J. Kari, Invited lecture (1)
16.30-17.30 M. Hochman, Invited lecture (1)
17.30-18.00 Coffee Break
18.00-18.30 Marcia Edson, Calculating the Garsia entropy in linear numeration systems, slides .
18.30-19.00 Manfred Madritsch, Non-normal numbers: The interplay of symbolic and topological dynamical systems, slides.
19.00-19.30 Milena Svobodova, Minimal digit sets for parallel addition in non-standard numeration systems, slides.

Tuesday, 22th May
9.00-10.00 N. Rampersad, Invited lecture (2)
10.00-10.30 Coffee Break
10.30-11.30 D. Perrin, Invited lecture (2)
11.30-12.30 C. Reutenauer, Invited lecture (1)
12.30-15.30 Lunch/Break
15.30-16.30 M. Crochemore, Invited lecture (2)
16.30-17.30 J. Kari, Invited lecture (2)
17.30-18.00 Coffee Break
18.00-18.30 Michael Schraudner, Multidimensional subshifts of finite type, slides.
18.30-19.00 Tyler White, Topologically mixing tiling of R2 generated by a generalized substitution, slides.
19.00-19.30 Nicolas Bedaride, Topological substitutions, slides.

Wednesday, 23th May
9.00-10.00 J. Kari, Invited lecture (3)
10.00-10.30 Coffee Break
10.30-11.30 M. Hochman, Invited lecture (2)
11.30-12.30 N. Rampersad, Invited lecture (3)
12.30-16.00 Lunch/Break
15.00-16.00 POSTER SESSION
16.00-16.30 Coffee Break
16.30-17.30 M. Crochemore, Invited lecture (3)
17.30-18.30 C. Reutenauer, Invited lecture (2)
18.30-19.00 Eric Rowland, Morphic words governing the boundaries of cellular automata, slides.
19.00-19.30 Pierre Nicodeme, Automata and combinatorics approaches for counting. An application to DNA evolution.

Thursday, 24th May
9.00-10.00 M. Crochemore, Invited lecture (4)
10.00-10.30 Coffee Break
10.30-11.30 J. Kari, Invited lecture (4)
11.30-12.30 M.-P. Béal, Invited lecture (3)
12.30-15.30 Lunch/Break
15.30-16.30 C. Reutenauer, Invited lecture (3)
16.30-17.30 M. Hochman, Invited lecture (3)
17.30-18.00 Coffee Break
18.00-18.30 Giulio Tiozzo, Tuning and plateaux for the entropy of alpha-continued fractions, slides.
18.30-19.00 Petr Kurka, Martin Delacourt, Fast arithmetical algorithms in Moebius number systems, slides.
19.00-19.30 Kevin Perrot, Kadanoff Sand Pile Model, slides.

Friday, 25th May
9.00-10.00 C. Reutenauer, Invited lecture (4)
10.00-10.30 Coffee Break
10.30-11.30 M. Hochman, Invited lecture (4)
11.30-12.30 N. Rampersad, Invited lecture (4)
12.30-14.00 Lunch/Break
14.00-15.00 M.-P. Béal, Invited lecture (4)

Abstracts

Dominique Perrin, Synchronized automata

Slides available here: part 1, part 2.

Marie-Pierre Béal, Road coloring

Slides available here: part 1, part 2.

We present recent insights in automata theory related to synchronizing sequences. Imagine a map with roads which are colored in such a way that a fixed sequence of colors, called a homing sequence or a synchronizing sequence, leads the traveler to a fixed place whatever be the starting point. Such a coloring of the roads is called synchronized. We first consider Cerny's Conjecture which says that the minimal length of a synchronizing sequence in an n-state synchronized colored (directed) graph is at most (n-1)^2. We present a proof of this conjecture in the particular case of aperiodic colored graphs which is due to Trahtman, and a recent result from Carpi and D'Alessandro for locally strongly transitive colored graphs. We then present Trahtman's Road Coloring Theorem for finding a synchronized coloring. The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. Finally, we show the importance of the existence of synchronizing sequences, or synchronizing patterns, in the domain of symbolic dynamics.

Maxime Crochemore, Text redundancies

Slides available here: part 1, part 2, part 3, part 4.

The talks discuss several questions related to redundancies in texts, regarded as sequences of symbols: repetitions, powers, runs, repeats, etc. Among the questions treated were the avoidability of long repetitions, bounds on the number of runs in words and efficient algorithms to compute all these redundancies.

Jarkko Kari, Cellular automata and Tilings

Slides available here: part 1, part 2, part 3, part 4.

Narad Rampersad, Repetitions in words

Lecture notes available here.

Slides available here: part 1, part 2, part 3, part 4.

We present a selection of topics concerning the avoidance of repetitions in words. We describe some of the main results concerning overlap-free binary words and we give an Fife-like characterization of these words. We also give an overview of the work leading to the resolution of Dejean's Conjecture. We give a short introduction to the use of the probabilistic method in combinatorics on words. We present a result of Carpi on the avoidance of repetitions in arithmetic progressions. We introduce the concept of Abelian repetitions and we illustrate a typical method for showing that a morphism generates a word avoiding Abelian repetitions. We explain the notion of "pattern" and illustrate a way of using generating functions to show the avoidability of certain patterns. Finally we describe some algorithmic results concerning automatic sequences.

Christophe Reutenauer, Linearly recursive sequences and Dynkin diagrams

Lecture notes available here.

Motivated by a construction in the theory of cluster algebras (Fomin and Zelevinsky), one associates to each acyclic directed graph a family of sequences of natural integers, one for each vertex; this construction is called a frieze; these sequences are given by nonlinear recursions (with division), and the fact that they are integers is a consequence of the Laurent phenomenon of Fomin and Zelevinsky. If the sequences satisfy a linear recursion with constant coefficients, then the graph must be a Dynkin diagram or an extended Dynkin diagram, with an acyclic orientation. The converse also holds: the sequences of the frieze associated to an oriented Dynkin or Euclidean diagram satisfy linear recursions, and are even N-rational. One uses in the proof objects called SL_2-tilings of the plane, which are fillings of the discrete plane such that each adjacent 2 by 2 minor is equal to 1. These objects, which application in the theory of cluster algebras, are interesting for themselves. Some problems, conjectures and exercises are given.

Mike Hochman, Symbolic dynamics, multidimensional subshifts, computability and arithmetic

Slides available here: part 1, part 2.

Lectures available here: lecture 3, lecture 4.

In this course we will discuss recent advances in the classification of the dynamics and certain invariants of combinatorial dynamical systems: by this we mean multidimensional shifts of finite type (Wang tiling systems), sofic shifts, and cellular automata. We will discuss combinatorial invariants, primarily entropy, and the classification of the numbers arising in this way. Then we will discuss the class of effective dynamical systems, which is the natural context within which to study combinatorial dynamical systems, the properties of the category, and invariants related to computability theory. Finally we will discuss the classification of (sub)dynamics of combinatorial dynamical systems.

The lectures will be organized as follows.

Lecture 1: Introduction to combinatorial dynamical systems, combinatorial invariants, and the arithmetic hierarchy of real numbers.

Lecture 2: Proof of the classification of entropies of shifts of finite type and cellular automata.

Lecture 3: Overview of topological dynamics, effective dynamical systems, computability degrees, basics results in the effective category.

Lecture 4: Classification of subdynamics and other results on combinatorial and effective dynamical systems.

Michael Schraudner, Entropy minimality of ${\mathbb Z}^d$ shifts of finite type (joint work with Samuel Lightwood)

It is well-known that an irreducible $\mathbb Z$ shift of finite type $X$ is always entropy minimal, i.e. that every proper subsystem of $X$ has strictly smaller entropy. While this result is very useful and has a lot of applications in the theory of one-dimensional subshifts, it does not extend to the class of ${\mathbb Z}^d$ subshifts for $d>1$. In the multidimensional setting only very strong uniform mixing conditions (e.g.\ UFP) guarantee entropy minimality, whereas non-entropy minimal still uniformly mixing (block or corner gluing) examples exist. In this talk we will show some of these non-entropy minimal examples called wire shifts, analyze the mechanism behind this phenomenon and we will give a necessary and sufficient condition characterizing entropy minimality of general ${\mathbb Z}^d$ shifts of finite type.

Nicolas Bedaride, Topological substitutions

We define 2-dimensional topological substitutions. A tiling of the Euclidean plane, or of the hyperbolic plane, is substitutive if the underlying 2-complex can be obtained by iteration of a 2-dimensional topological substitution. We give examples of substitutive tilings of the euclidean plane or the hyperbolic plane.

Kevin Perrot, Kadanoff Sand Pile Model

Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. The main interest of sand piles relies in their Self Organized Criticality (SOC), the property that a small perturbation --- adding some sand grains --- on a fixed configuration has unbounded consequences on the system, involving an arbitrary number of grain fall. Physicists L. Kadanoff et al. inspire KSPM, a model presenting a sharp SOC behavior, extending the well known Sand Pile Model. In KSPM(D), we start from a pile of N stacked grains and apply the rule: D-1 grains can fall from column i onto the D-1 adjacent columns to the right if the difference of height between columns i and i+1 is greater or equal to D. Toward the study of fixed points (stable configurations on which no rule can be applied) obtained from N stacked grains, we propose an iterative study of KSPM evolution consisting in the repeated addition of one single grain on a heap of sand, triggering an avalanche at each iteration. We develop a formal background for the study of avalanches, resumed in a finite state word transducer, and explain how this transducer may be used to predict the form of fixed points. Further precise developments provide a plain formula for fixed points of KSPM(3), showing the emergence of a wavy shape.