Du lundi 6 septembre au vendredi 10 septembre 2010, à AMIENS (France).
Lundi  Mardi  Mercredi  Jeudi  Vendredi  
9h  Exposé invité Franck PETIT Deaf and dumb robots & Words 
Exposé invité JeanÉric PIN The abstract notion of recognition: algebra, logic and topology 
Exposé invité Mathieu SABLIK Simulating an effective subshift by a subshift of finite type: some applications 
Exposé invité Thierry LECROQ Indexing Structures and Next Generation Sequencing (NGS) 

10h 
Accueil des participants  Pause Café  Pausé Café  Pause Café  Pause Café 
10h30 
Antonio Restivo, Giovanna Rosone. On the product of balanced sequences  Pedro V. Silva. The automatatheoretic approach to fixed points of endomorphisms  Tomas Hejda. Morphisms preserving the set of words coding three interval exchange  Alexandre Decan, Véronique Bruyère, Olivier Gauwin, Jef Wijsen and Olivier Carton. A Variant of Pattern Matching for Multiwords  
11h 
Alexandre Blondin Massé, Geneviève Paquin and Laurent Vuillon. A Fine and Wilf's theorem for pseudoperiods and Justin's formula for generalized pseudostandard words  VinhDuc Tran and Igor Litovsky. Onerelation languages and omegacode generators  Julien Leroy. Some improvements of the Sadic conjecture (extended abstract)  Edmunds Cers. An unique basis representation of finitely generated biideals  
11h30 
Francine BlanchetSadri, Amelia Tebbe and Amy Veprauskas. Fine and Wilf's Theorem for Abelian Periods in Partial words  Janis Buls and Edmunds Cers. Modularity in the semilattice of omegawords  Maurice Margenstern. An application of iterative pushdown automata to contour words of balls and truncated balls in hyperbolic tessellations  Gabriele Fici. Special factors and factor automata  
12h 
Clôture des journées  
12h30 

13h  Accueil des participants  
13h30 

14h  Ouverture des journées  Exposé invité Alejandro MAASS [New Title] Rigidity results in cellular automata theory: probabilistic and ergodic approach 
Wit Forys and Piotr Oprocha. Symbolic Dynamics on Infinite Traces  Minimal Shift Case and Flower Shift Case  Exposé invité Juhani KARHUMÄKI Local vs global regularity of words and automata theory 
Événement satellite PAVAGES  ANR Subtile 
Exposé invité Narad RAMPERSAD Repetitions in Words: Classical and Recent Results 

14h30  Matthieu Deneufchâtel. How to compute Selberglike integrals?  
15h  Petr Ambroz, Daniel Dombek, Zuzana Masáková and Edita Pelantová. Numbers with integer expansion in the numeration system with negative base  Tarek Sellami^{*}. Common dynamics of Pisot Substitutions  Golnaz Badkobeh and Maxime Crochemore. Fewest repetitions in infinite binary words  
Michel Goemans and Raphaël Jungers. The synchronizing probability function of an automaton  
15h30  Pause Café  Sortie culturelle : visite guidée de la Cathédrale d'Amiens  Pause Café  
Pause Café  
16h  PierreYves Angrand and Jacques Sakarovitch. On the enumerating series of an abstract numeration system  Alexey Samsonov and Arseny Shur. On Abelian Repetition Threshold  
Anna Frid and Luca Zamboni. On automatic infinite permutations  
16h30  Karel Klouda and Christiane Frougny. Rational base number systems for padic numbers  Pascal Ochem and Elise Vaslet. Repetition thresholds for subdivided graphs and trees  
Laura Giambruno and Sabrina Mantaci. State complexities of transducers for bidirectional decoding of prefix codes  
17h  Rafik Belhadef and HenriAlex Esbelin. Transcendence and padic continued fractions  Svetlana Puzynina, Sergey Avgustinovich and Juhani Kahumäki. On abelian versions of Critical Factorization Theorem  
Emilie Charlier, Narad Rampersad, Michel Rigo and Laurent Waxweiler. Structure of the minimal automaton of a numeration language, and: State complexity of testing divisiblity  
17h30  
18h  Pot d'accueil  
19h Banquet  
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. 12, 153167.
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 nonempty 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 onedimensional 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.
Revenir au programme 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.
Revenir au programmeMathieu 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.
Revenir au programmeNarad Rampersad
Title: Repetitions in Words: Classical and Recent Results
Abstract: In his 1906 and 1912 papers, Axel Thue initiated the study of repetitions in wordsor 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.
Revenir au programmeThierry 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.
Revenir au programme