On the maximal number of cubic subwords in a string

Details On the maximal number of cubic subwords in a string On the maximal number of cubic subwords in a string

2009-11-06

arxiv.org/abs/0911.1370v1

Computer Science

Formal Languages and Automata Theory

14 pages

Scientific paper

We investigate the problem of the maximum number of cubic subwords (of the form $www$) in a given word. We also consider square subwords (of the form $ww$). The problem of the maximum number of squares in a word is not well understood. Several new results related to this problem are produced in the paper. We consider two simple problems related to the maximum number of subwords which are squares or which are highly repetitive; then we provide a nontrivial estimation for the number of cubes. We show that the maximum number of squares $xx$ such that $x$ is not a primitive word (nonprimitive squares) in a word of length $n$ is exactly $\lfloor \frac{n}{2}\rfloor - 1$, and the maximum number of subwords of the form $x^k$, for $k\ge 3$, is exactly $n-2$. In particular, the maximum number of cubes in a word is not greater than $n-2$ either. Using very technical properties of occurrences of cubes, we improve this bound significantly. We show that the maximum number of cubes in a word of length $n$ is between $(1/2)n$ and $(4/5)n$. (In particular, we improve the lower bound from the conference version of the paper.)

Affiliated with

Also associated with

No associations

Rating

On the maximal number of cubic subwords in a string 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 On the maximal number of cubic subwords in a string, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the maximal number of cubic subwords in a string will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-699348