Maximal Complexity of Finite Words

الأصل · EN

The subword complexity of a finite word w of length N is a function which associates to each n≤ N the number of all distinct subwords of w having the length n. We define the maximal complexity C(w) as the maximum of the subword complexity for n ∈ {1,2,..., N }, and the global maximal complexity K(N) as the maximum of C(w) for all words w of a fixed length N over a finite alphabet. By R(N) we will denote the set of the values i for which there exits a word of length N having K(N) subwords of length i. M(N) represents the number of words of length N whose maximal complexity is equal to the global maximal complexity.