Name
Abstract | ||
|---|---|---|
A weak square in a binary word is a pair of adjacent nonempty blocks of the same length, having the same number of 1s. A weak circular square is a weak square which is possibly wrapped around the word: the tail protruding from the right end of the word reappears at the left end. Two weak circular squares are equivalent if they have the same length and contain the same number of ones. We prove that the longest word with only k inequivalent weak circular squares contains 4k+2 bits and has the form (01)2k+1 or its complement. Possible connections to tandem repeats in the human genome are pointed out. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/3-540-63220-4_51 | CPM |
Keywords | Field | DocType |
right end,longest word,weak square,left end,k inequivalent,human genome,weak circular squares,weak circular square,word reappears,binary words,adjacent nonempty block,binary word | Tandem repeat,Discrete mathematics,Combinatorics,Combinatorial analysis,Pattern matching,Mathematics,Binary number | Conference |
Volume | ISSN | ISBN |
1264 | 0302-9743 | 3-540-63220-4 |
Citations | PageRank | References |
1 | 0.37 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aviezri S. Fraenkel | 1 | 559 | 164.51 |
| Jamie Simpson | 2 | 164 | 21.41 |
| Mike Paterson | 3 | 744 | 152.22 |