F Nous contacter


0

Documents  05A05 | enregistrements trouvés : 4

O
     

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

La décomposition par substitution des permutations permet de voir ces objets combinatoires comme des arbres. Je présenterai d'abord cette décomposition par substitution, et les arbres sous-jacents, appelés arbres de décomposition. Puis j'exposerai une méthode, complètement algorithmique et reposant sur les arbres de décomposition, qui permet de calculer des spécifications combinatoires de classes de permutations à motifs interdits. La connaissance de telles spécifications combinatoires ouvre de nouvelles perspectives pour l'étude des classes de permutations, que je présenterai en conclusion. La décomposition par substitution des permutations permet de voir ces objets combinatoires comme des arbres. Je présenterai d'abord cette décomposition par substitution, et les arbres sous-jacents, appelés arbres de décomposition. Puis j'exposerai une méthode, complètement algorithmique et reposant sur les arbres de décomposition, qui permet de calculer des spécifications combinatoires de classes de permutations à motifs interdits. La c...

68-06 ; 05A05

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

Multi angle  $k$-abelian complexity and fluctuation
Saarela, Aleksi (Auteur de la Conférence) | CIRM (Editeur )

Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.

First, we look at minimal and maximal complexity. Studying minimal complexity leads to results on ultimately periodic and Sturmian words, similar to the results by Morse and Hedlund on the usual factor complexity. Maximal complexity is related to counting the number of equivalence classes. As a more complicated topic, we study the question of how much k-abelian complexity can fluctuate between fast growing and slowly growing values. These questions could naturally be asked also in a setting where we restrict our attention to some subclass of all words, like morphic words.
Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.

First, we look at minimal and maximal ...

68Q45 ; 68R15 ; 05A05

Nuage de mots clefs ici

Z