Super-d-complexity of finite words

Details Super-d-complexity of finite words Super-d-complexity of finite words

2011-04-22

arxiv.org/abs/1104.4424v1

8th Joint Conf. on Math. and Comp. Sci. July 14--17, 2010, Kom\'arno, Slovakia, Selected papers, 2011. pp. 251--261

Computer Science

Discrete Mathematics

Scientific paper

In this paper we introduce and study a new complexity measure for finite words. For positive integer $d$ special scattered subwords, called super-$d$-subwords, in which the gaps are of length at least $(d-1)$, are defined. We give methods to compute super-$d$-complexity (the total number of different super-$d$-subwords) in the case of rainbow words (with pairwise different letters) by recursive algorithms, by mahematical formulas and by graph algorithms. In the case of general words, with letters from a given alphabet without any restriction, the problem of the maximum value of the super-$d$-complexity of all words of length $n$ is presented.

Affiliated with

Also associated with

No associations

Rating

Super-d-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 Super-d-complexity of finite words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Super-d-complexity of finite words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-330707