Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  Palindromes patterns
Brlek, Srecko (Auteur de la Conférence) | CIRM (Editeur )

The study of palindromes and their generalizations in a word has gained a lot of interest in the last 20 years, motivated by applications in physics, biology, discrete geometry, to name only a few. Using Sebastien Ferenczi as an example, we illustrate the computation of its palindromic complexity and its relation with the usual factor complexity, via an identity attributed to Brlek and Reutenauer involving also the palindromic defect. Periodic infinite words as well as the family of words with language closed by reversal also satisfy the identity. The identity remains valid when palindromic is replaced by $\sigma$-palindromic, and we also discuss some other patterns. The study of palindromes and their generalizations in a word has gained a lot of interest in the last 20 years, motivated by applications in physics, biology, discrete geometry, to name only a few. Using Sebastien Ferenczi as an example, we illustrate the computation of its palindromic complexity and its relation with the usual factor complexity, via an identity attributed to Brlek and Reutenauer involving also the palindromic defect. Periodic ...

68Q45 ; 68R15

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  Independence of normal words
Becher, Verónica (Auteur de la Conférence) | CIRM (Editeur )

Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1. We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. We construct a word x such that the symbol at position n is equal to the symbol at position 2n. Thus, x is the join of x itself and the subsequence of odd positions of x. We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.
This is joint work with Olivier Carton (Universitéé Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).
Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has ...

68R15 ; 11K16 ; 03D32

Filtrer

Type
Domaine
Codes MSC

Z
,toolbar=no,scrollbars=yes")'>Signaler une erreur

1

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  From combinatorial games to shape-symmetric morphisms
Rigo, Michel (Auteur de la Conférence) | CIRM (Editeur )

The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.
In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review some of their characterizations (in terms of morphisms, finiteness of their k-kernel,...). These sequences take values in a finite set but the Sprague-Grundy function of a game, such as Nim of Wythoff, is usually unbounded. This provides a motivation to introduce k-regular sequences (in the sense of Allouche and Shallit) whose k-kernel is not finite, but finitely generated.
In the second lecture, games played on several piles of token naturally give rise to a multi-dimensional setting. Thus, we reconsider k-automatic and k-regular sequences in this extended framework. In particular, determining the structure of the bidimensional array encoding the (loosing) P-positions of the Wythoff’s game is a long-standing and challenging problem in CGT. Wythoff’s game is linked to non-standard numeration system: P-positions can be determined by writing those in the Fibonacci system. Next, we present the concept of shape-symmetric morphism: instead of iterating a morphism where images of letters are (hyper-)cubes of a fixed length k, one can generalize the procedure to images of various parallelepipedic shape. The shape-symmetry condition introduced twenty years ago by Maes permits to have well-defined fixed point.
In the last lecture, we move to generalized numeration systems: abstract numeration systems (built on a regular language) and link them to morphic (multidimensional) words. In particular, pictures obtained by shape-symmetric morphisms coincide with automatic sequences associated with an abstract numeration system. We conclude these lectures with some work in progress about games with a finite rule-set. This permits us to discuss a bit Presburger definable sets.
The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.
In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review ...

91A46 ; 68R15 ; 68Q45

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  Avoiding $k$-abelian powers in words
Rao, Michaël (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  On $k$-abelian palindromes
Puzynina, Svetlana (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  $k$-abelian equivalence: an equivalence relation in between the equality and the abelian equivalence
Karhumäki, Juhani (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  Exemple d'Arnoux-Yoccoz, fractal de Rauzy, problème de Novikov : brins d'une guirlande éternelle
Hubert, Pascal (Auteur de la Conférence) | CIRM (Editeur )