Auteurs : Saarela, Aleksi (Auteur de la Conférence)
CIRM (Editeur )
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 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
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
|
Voir aussi
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