The Factor Complexity And Permutation Complexity Of Several Sequences

This paper studies the properties of sequences generated by substitution and its application in factor complexity and permutation complexity. Substitution effect on the alphabet will generate substitution sequence, substitution is the main and the most effective way to generate sequence. The study of substitution has a long history. In the 60’s and 70’s, the research of sequence is mostly about automata theory and the application of power system and its contact. In the 80’s, people gradually found the connection between substitution sequence and harmonic analysis, fractal geometry, number theory, physics, portfolio analysis, thus attracted the attention of the various discipline relevant workers. The combination properties of some famous infinite words over the binary character table is introduced by A.T hue, and then found by several other authors. The research of factor complexity is early and have obtained a lot of satisfactory results. The study of the infinite permutations generated by sequences over a finite alphabet is relatively new. The original study of infinite permutation generated by a sequence has been attributed to A.E.F ride, a lot of results followed were given.This paper studies the factor complexity of the Chacon sequence and the special sequence and the permutation complexity of the special sequence. Firstly we introduce the definitions and related properties of word and factor, and then the definition and characteristics of the sequence are given, at last we obtain factor complexity and the permutation complexity of the Chacon sequence and the special sequence.In the second chapter, we introduce the definition and some properties related to word,factor, factor complexity, permutation complexity. In the third chapter, that is the main part of this article, through the law of the right special factors in the two sequences and the sequences based on the relationship between the right special factors and the factor complexity of a sequence, which gives the specific factor complexity formulas of the Chacon sequence and the special sequences. Finally, through the factor complexity of the special sequence we get the permutation complexity of the special sequence.At the end of the article we give right special factors and factors of the Chacon sequence and special sequences and some factors of special sequence which can generate two different permutations.