A4 Refereed article in a conference publication
On growth and fluctuation of k-abelian complexity
Authors: Julien Cassaigne, Juhani Karhumäki, Aleksi Saarela
Editors: Lev D. Beklemishev, Daniil V. Musatov
Conference name: International Computer Science Symposium in Russia
Publication year: 2015
Journal: Lecture Notes in Computer Science
Book title : Computer Science -- Theory and Applications: 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings
Series title: Lecture Notes in Computer Science
Volume: 9139
First page : 109
Last page: 122
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-20297-6_8
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
