Name
Abstract | ||
|---|---|---|
The well-known periodicity lemma of Fine and Wilf states that if the word x of length n has periods p, q satisfying p + q - d 驴 n, then x has also period d, where d = gcd(p, q). Here we study the case of long periods, namely p+ q - d n, for which we construct recursively a sequence of integers p = p1 p2 ... pj-1 2, such that x1, up to a certain prefix of x1, has these numbers as periods. We further compute the maximum alphabet size |A| = p+ q - n of A over which a word with long periods can exist, and compute the subword complexity of x over A. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-48194-X_8 | CPM |
Keywords | Field | DocType |
periods p,length n,longer periods,q satisfying p,certain prefix,invited lecture,long period,subword complexity,maximum alphabet size,wilf state,periodicity lemma,p1 p2,integers p,satisfiability | Integer,Discrete mathematics,Combinatorics,Prefix,Recursion,Lemma (mathematics),Mathematics,Alphabet | Conference |
ISBN | Citations | PageRank |
3-540-42271-4 | 2 | 0.57 |
References | Authors | |
1 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aviezri S. Fraenkel | 1 | 559 | 164.51 |
| Jamie Simpson | 2 | 164 | 21.41 |