On growth and fluctuation of k-abelian complexity



: Julien Cassaigne, Juhani Karhumäki, Aleksi Saarela

: Lev D. Beklemishev, Daniil V. Musatov

: International Computer Science Symposium in Russia

: 2015

: Lecture Notes in Computer Science

: Computer Science -- Theory and Applications: 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings

: Lecture Notes in Computer Science

: 9139

: 109

: 122

: 0302-9743

DOI: https://doi.org/10.1007/978-3-319-20297-6_8

: https://research.utu.fi/converis/portal/detail/Publication/3114388


An extension of abelian complexity, so called k-abelian complexity, has been considered recently in a number of articles. This paper considers two particular aspects of this extension: First, how much the complexity can increase when moving from a level k to the next one. Second, how much the complexity of a given word can fluctuate. For both questions we give optimal solutions.


Last updated on 2024-26-11 at 15:10