Maximal Complexity of Finite Words

Details Maximal Complexity of Finite Words Maximal Complexity of Finite Words

2010-02-13

arxiv.org/abs/1002.2724v1

Pure Math. Appl., 13, 1-2 (2002) pp. 39-48

Computer Science

Discrete Mathematics

Scientific paper

The subword complexity of a finite word $w$ of length $N$ is a function which associates to each $n\le N$ the number of all distinct subwords of $w$ having the length $n$. We define the \emph{maximal complexity} C(w) as the maximum of the subword complexity for $n \in \{1,2,..., N \}$, and the \emph{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.

Affiliated with

Also associated with

No associations

Rating

Maximal Complexity of Finite Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximal Complexity of Finite Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximal Complexity of Finite Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-324134