Du lundi 6 septembre au vendredi 10 septembre 2010, à AMIENS (France).
Deaf and dumb robots & Words
The abstract notion of recognition: algebra, logic and topology
Simulating an effective subshift by a subshift of finite type: some applications
Indexing Structures and Next Generation Sequencing (NGS)
||Accueil des participants||Pause Café||Pausé Café||Pause Café||Pause Café|
||Antonio Restivo, Giovanna Rosone. On the product of balanced sequences||Pedro V. Silva. The automata-theoretic 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|
||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||Vinh-Duc Tran and Igor Litovsky. One-relation languages and omega-code generators||Julien Leroy. Some improvements of the S-adic conjecture (extended abstract)||Edmunds Cers. An unique basis representation of finitely generated bi-ideals|
||Francine Blanchet-Sadri, 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 omega-words||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|
||Clôture des journées|
|13h||Accueil des participants|
|14h||Ouverture des journées||Exposé invité
[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é
Local vs global regularity of words and automata theory
|Événement satellite PAVAGES - ANR Subtile|
Repetitions in Words: Classical and Recent Results
|14h30||Matthieu Deneufchâtel. How to compute Selberg-like 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é|
|16h||Pierre-Yves 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 p-adic 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 Henri-Alex Esbelin. Transcendence and p-adic 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|
Title: Local vs global regularity of words and automata theory
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 , 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.
 Mignosi, Filippo; Restivo, Antonio; Salemi, Sergio. Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998), no. 1-2, 153-167.
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
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.
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.Revenir au programme
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 programme
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 programme
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.Revenir au programme
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