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) |
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.