The Study Of Different Kinds Of Complexity Functions Of Infinite Words

The main topics of interest in this paper will be three types of complexity of infinite words,permutation complexity,abelian complexity,k-ablian complexity.Permutation com-plexity and abelian complexity have been investigated over the past decades.The k-abelian complexity is a relatively new area in combinatorics on words.In this thesis,we mainly concert about two kinds of sequences:the Cantor-like sequences and the Rudin-Shapiro sequence.Specifically speaking,first,by using the properties of right special factors of the Cantor-like sequence,we computed the permutation complexity of the Cantor-like sequence,proved the regularity of the difference sequence of the permutation complexity,gave the generalized automaton generating the difference sequence and proved the regularity of the permutation complexity of the Cantor-like sequence.Second,we studied the property of the partial sum of the Rudin-Shapiro sequence and proved the regularity of the abelian com-plexity of the Rudin-Shapiro sequence by using the relation between the partial sum and the abelian complexity of infinite words over an alphabet consisting of two letters.And we computed the box dimension of the graph of the asymptotic function of the abelian com-plexity.Last,we studied the k-abelian complexity of the Cantor sequence and proved that the k-abelian complexity of the Cantor sequence is regular.By using the decidable properties of automatic sequences,Shallit,Rampersad,Char-lier proved the following result:The permutation complexity of a k-automatic sequence is(N,k)-regular.In the third chapter,using the properties of the factors of the Cantor-like sequence,we gave out the concrete formulas for the permutation complexity of the Cantor-like sequence,proved the regularity of the difference of the permutation complexity and the regularity of the permutation complexity.Moreover,we checked the rightness of their results.Rampersad,Madill proved that the abelian complexity of the paper-folding sequence is 2-regular and proposed the following open question:Is the abelian complexity function of a k-automatic sequence always k-regular?The question cannot be solved by using the decidable theory of Shallit.To the best of our knowledge,it is still unsolved.In the fourth chapter,first,we studied the property of the partial sum of the Rudin-Shapiro sequence and proved the regularity of the abelian complexity of the Rudin-Shapiro sequence by using the relation between the partial sum and the abelian complexity of infinite words over an alphabet consisting of two letters.This gives a positive example for their question.Second,we made the abelian complexity function of the Rudin-Shapiro sequence continuously and got a new function.We studied the continuity,differentiability and the box dimension of the graph of the new function.In 2013,Karhumaki,Saarela and Zamboni extended the notation of abelian complexity to k-ablian complexity and computed the k-abelian complexity of all Sturmain sequences.In 2014,Vandomme,Parreau and Rigo proposed a conjecture:The 2-abelian complexity of the Thue-Morse sequence is 2-regular.The conjecture was solved by Greinecker and Rigo using different methods.In the paper of Greinecker,he also conjectured that the 2-abelian complexity of every p-automatic sequence is p-regular.In the fifth chapter,we studied the k-abelian complexity of the Cantor-like sequence,where k?Z+ ?{+?}.Finally,we proved that the k-abelian complexity of the Cantor sequence is regular,which gave another positive example for the conjecture of Greinecker.In the last chapter,we summarized the main results.Then,we came up with some further research corresponding to our topics.