Juhani Karhumäki
Title: Local vs global regularity of words and automata theory

Abstract: One of the fundamental topics in mathematics is search for relations between local and global regularities. We analyze this phenomena in connection with infinite words. Local regularity here means that the word possesses everywhere some local (finitely describable) regularity condition, such as some type of local periodicity, while the global regularity means that the word is periodic (or ultimately periodic).
More concretely, local periodicity could be that each long enough suffix of the word ends up with a square or with cube, respectively. In the case of squares the local regularity does not imply the ultimate periodicity, while the cubes do so. A striking exact border of order of repetitions in this setting was shown by Mignosi, Restivo and Salemi, see [1], where it is also shown that the Fibonacci word proves the optimality.
We analyze this problem area in several concrete different settings, including some where Abelian repetitions are considered instead as ordinary repetitions as models of local regularity. In particular, finite automata are very useful tools in solving and describing these phenomena.This is further emphasized by the following property: In many, if not all, natural cases if a local property need not imply the ultimate periodicity, then there are nondenumerably many words (or objects) satisfying this local property - which is directly visible from the structure of the corresponding automaton. The nondenumerability of such objects justifies our terminology stating that the local property allows a chaotic behaviour. In this terminology ultimately periodic words can be viewed as predictable. In this view we are looking for local properties which would separate predictable and chaotic behaviours in infinite words.

[1] Mignosi, Filippo; Restivo, Antonio; Salemi, Sergio. Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998), no. 1-2, 153-167.

Franck Petit
Main Title : Deaf and Dumb Robots & Words
Subtitle: On the Impact of Lyndon Words in the Distributed Coordination of a Set of Autonomous Mobile Robots

Abstract: In a given environment, the ability for the swarm of robots to succeed in the accomplishment of the assigned task greatly depends on global properties assigned to the swarm, and individual capabilities each robot has. Examples of such global properties are the ability to distinguish among themselves at least one (or, more) robots (leader), to agree on a common global direction (sense of direction), to remember any previous observation or computation performed in previous steps, or to agree on a common handedness (chirality). The individual capacities of each robot are its moving capabilities and its sensory organs.
To deal with cost, flexibility, resilience to dysfunction, and autonomy, many problems arise for handling the distributed coordination of swarms of robots in a deterministic manner. This issue is motivated by the minimal level of ability that the robots are required to have in the accomplishment of basic cooperative tasks. In other words, the feasibility of some given tasks is addressed assuming swarm of autonomous robots either devoid or not of capabilities like (observable) identifiers, direct means of communication, means of storing previous observations, sense of direction, chirality, etc.
Leader election (LE) and arbitrary pattern formation (APF) are fundamental tasks for a set of autonomous mobile robots. The former consists in moving the system from an initial configuration were all entities are in the same state into a final configuration were all entities are in the same state, except one, the leader. The latter consists in the design of protocols allowing autonomous mobile robots to form any (arbitrary) geometric pattern. The solvability of both these tasks turns out to be necessary in order to achieve more complex tasks.
During this talk, we address both problems (i.e., LE and APF) and Lyndon words. A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. We show that Lyndon words enter for a large part in the deterministic solvability of both problems. More precisely, they are the basis of a complete characterization (necessary and sufficient conditions) on the robots positions to deterministically elect a leader. We show that Leader Election and Pattern Formation are two equivalent problems in the precise sense that, the former is solvable if and only if the latter problem is solvable.

Alejandro Maass
Title: Rigidity results in cellular automata theory: probabilistic and ergodic approach.

Abstract: The objective of this talk is to review the some now claassical and new results and its extensions concerning the existence of invariant stationary probability measures under a one-dimensional algebraic cellular automaton. We present two historical axes of this question and the techniques used to solve them or produce relevant intermediate results. Both make appear strong rigidity phenomena, i.e. the unique solution is the uniform Bernoulli product measure. The rst axe is the ergodic theory approach where we impose some natural conditions on the entropy and ergodicity of the system to get the result. This approach follows ideas by Rudolph and Host in the classical problem called ( ×2, ×3) in the circle posed by Hillel Furstenberg at the end of the 60. Then we present a purely probabilistic approach. We study the convergence of the Cesàro mean of the iterates by a cellular automaton of a translation invariant probability measure. Assuming some natural correlation properties (this class includes Markov and Gibbs probability measures of full topological support) one proves the limit exists and it is the uniform Bernoulli product measure.

Jean-Éric Pin
Title: The abstract notion of recognition: algebra, logic and topology
(joint work with M. Gehrke and S. Grigorieff)

After a brief survey of the classical notions, we shall propose a new approach to the notion of recognition, which departs from the classical definitions by three specific features. First, it does not rely on automata. Secondly, it applies to any lattice of subsets rather than to individual subsets. Thirdly, topology is the key ingredient. Potential applications to language theory and logic will be discussed.

Mathieu Sablik
Title: Simulating an effective subshift by a subshift of finite type: some applications

We study how a subshift can simulate another one, where the notion of simulation is given by operations on subshifts inspired by the dynamical systems theory (factor, projective subaction...). There exists a correspondence between this notion of simulation and the set of forbidden patterns. In particular, every effective subshift (that is to say that forbidden patterns are given by a Turing machine) can be simulated by a SFT (that is to say a tiling) using subaction and factor. This construction can be used to obtain interesting properties.

Narad Rampersad
Title: Repetitions in Words: Classical and Recent Results

Abstract: In his 1906 and 1912 papers, Axel Thue initiated the study of repetitions in words---or rather, the avoidance of repetitions in words. He proved that using only 3 symbols, one can construct an infinite sequence of symbols containing no repetition of the form xx. Since then, many researchers have extended Thue's work in different directions. For example, Paul Erdos asked if there exists an infinite sequence, using only a finite number of symbols, containing no "Abelian repetition", that is, a repetition of the form xy, where y is a rearrangement of the symbols of x. Another generalization of "repetition" came from Francoise Dejean, who asked in 1972 whether certain "fractional repetitions" were avoidable over a given alphabet. This led to her famous conjecture on the "repetition threshold", which was finally proved in 2009 by the cumulative work of several researchers. We present several of these generalizations of Thue's problem and discuss some of the main results, such as the resolution of Dejean's conjecture. We also look at some recent extensions of the study of repetitions in words to the study of repetitions in other combinatorial structures, such as graph colourings, etc.

Thierry Lecroq
Title: Indexing Structures and Next Generation Sequencing (NGS)

In biology, new high throughput sequencing technologies aka Next Generation Sequencing (NGS) enable to produce gigantic masses of data at relatively low costs and short time. The raw data coming out of the sequencers are very short (compared to the whole genome) sequences (around 100 base pairs) called reads. One experiment usually outputs several millions of reads. Thus, even more than speed, space is an issue for efficiently process all these data. In this talk we will review some of the more recent results on data structures for indexing either the genomes or the reads.