Abstract : 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.
Recording during the thematic meeting: "Combinatorics on Words" the March 16, 2016 at the Centre International de Rencontres Mathématiques (Marseille, France)
Filmmaker: Guillaume Hennenfent
Find this video and other talks given by worldwide mathematicians on CIRM's Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities:
- Chapter markers and keywords to watch the parts of your choice in the video
- Videos enriched with abstracts, bibliographies, Mathematics Subject Classification
- Multi-criteria search by author, title, tags, mathematical area
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.
Recording during the thematic meeting: "Combinatorics on Words" the March 16, 2016 at the Centre International de Rencontres Mathématiques (Marseille, France)
Filmmaker: Guillaume Hennenfent
Find this video and other talks given by worldwide mathematicians on CIRM's Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities:
- Chapter markers and keywords to watch the parts of your choice in the video
- Videos enriched with abstracts, bibliographies, Mathematics Subject Classification
- Multi-criteria search by author, title, tags, mathematical area
Aleksi Saarela : k-abelian complexity and fluctuation cnrs montpellier | |
5 Likes | 5 Dislikes |
111 views views | 10K followers |
Science & Technology | Upload TimePublished on 6 Apr 2016 |
No comments:
Post a Comment