Name
Abstract | ||
|---|---|---|
We investigate the problem of the maximum number of different 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 presented 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 @?n2@?-1, and the maximum number of subwords of the form x^k, for k=3, is exactly n-2. In particular, the maximum number of cubes in a word is not greater than n-2 either. Using 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 12n-2n and 45n. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ejc.2012.07.012 | Eur. J. Comb. |
Keywords | Field | DocType |
primitive word,new result,nontrivial estimation,nonprimitive square,form ww,square subwords,length n,different cubic subwords,maximum number,simple problem | Discrete mathematics,Combinatorics,Of the form,Upper and lower bounds,Mathematics,Cube | Journal |
Volume | Issue | ISSN |
34 | 1 | 0195-6698 |
Citations | PageRank | References |
3 | 0.49 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Kubica | 1 | 30 | 2.52 |
| jakub radoszewski | 2 | 32 | 2.90 |
| wojciech rytter | 3 | 130 | 17.13 |
| Tomasz Waleń | 4 | 706 | 39.62 |