En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1 6

$k$-abelian complexity and fluctuation

Sélection Signaler une erreur
Multi angle
Auteurs : Saarela, Aleksi (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...

Résumé : 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.

Codes MSC :
05A05 - Permutations, words, matrices
68Q45 - Formal languages and automata
68R15 - Combinatorics on words

    Informations sur la Vidéo

    Langue : Anglais
    Date de publication : 31/03/16
    Date de captation : 16/03/16
    Sous collection : Research talks
    arXiv category : Combinatorics ; Discrete Mathematics
    Domaine : Combinatorics ; Computer Science
    Format : MP4 (.mp4) - HD
    Durée : 00:21:29
    Audience : Researchers
    Download : https://videos.cirm-math.fr/2016-03-16_Saarela.mp4

Informations sur la Rencontre

Nom de la rencontre : Combinatorics on words / Combinatoire des mots
Organisateurs de la rencontre : Cassaigne, Julien ; Nowotka, Dirk
Dates : 14/03/16 - 18/03/16
Année de la rencontre : 2016
URL Congrès : http://conferences.cirm-math.fr/1429.html

Données de citation

DOI : 10.24350/CIRM.V.18945503
Citer cette vidéo: Saarela, Aleksi (2016). $k$-abelian complexity and fluctuation. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18945503
URI : http://dx.doi.org/10.24350/CIRM.V.18945503

Bibliographie

  • Cassaigne, J., Karhumäki, J., & Saarela, A. (2015). On growth and fluctuation of k-abelian complexity. In L.D. Beklemishev, & D.V. Musatov (Eds.), Computer science: theory and applications (pp. 109-122). Cham: Springer - http://dx.doi.org/10.1007/978-3-319-20297-6_8

  • Karhumäki, J., Saarela, A., & Zamboni, L.Q. (2013). On a generalization of Abelian equivalence and complexity of infinite words. Journal of Combinatorial Theory. Series A, 120(8), 2189-2206 - http://dx.doi.org/10.1016/j.jcta.2013.08.008



Sélection Signaler une erreur