Logo image
Back
A New Periodicity Lemma
Journal article   Peer reviewed

A New Periodicity Lemma

K. Fan, S.J. Puglisi, W.F. Smyth and A. Turpin
SIAM Journal on Discrete Mathematics, Vol.20(3), pp.656-668
2006
DOI: https://doi.org/10.1137/050630180
url
Link to Published Version *Subscription may be requiredView

Abstract

Given a string $\s{x}=\s{x}[1..n]$, a repetition of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r = \break {\mbox{\boldmath x}}[i..i\+ rp\- 1]$, $p = |{\mbox{\boldmath u}}|$, $r \ge 2$, where neither ${\mbox{\boldmath u}} = {\mbox{\boldmath x}}[i..i\+ p\- 1]$ nor ${\mbox{\boldmath x}}[i..i\+ (r\+ 1)p\- 1]$ is a repetition. The maximum number of repetitions in any string {\mbox{\boldmath x}} is well known to be $\Theta(n\log n)$. A run or maximal periodicity of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r{\mbox{\boldmath t}} = {\mbox{\boldmath x}}[i..i\+ rp\+ |{\mbox{\boldmath t}}|\- 1]$ of {\mbox{\boldmath x}}, where ${\mbox{\boldmath u}}^r$ is a repetition, {\mbox{\boldmath t}} is a proper prefix of {\mbox{\boldmath u}}, and no repetition of period p begins at position $i\- 1$ of {\mbox{\boldmath x}} or ends at position $i\+ rp\+ |{\mbox{\boldmath t}}|$. In 2000 Kolpakov and Kucherov [J. Discrete Algorithms, 1 (2000), pp. 159–186] showed that the maximum number $\rho(n)$ of runs in any string {\mbox{\boldmath x}} is $O(n)$, but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data strongly suggesting that $\rho(n) < n$. Related work by Fraenkel and Simpson [J. Combin. Theory Ser. A., 82 (1998), pp. 112–120] showed that the maximum number $\sigma(n)$ of distinct squares in any string {\mbox{\boldmath x}} satisfies $\sigma(n) < 2n$, while experiment again encourages the belief that in fact $\sigma(n) < n$. In this paper, as a first step toward proving these conjectures, we present a periodicity lemma that establishes limitations on the number and range of periodicities that can occur over a specified range of positions in {\mbox{\boldmath x}}. We then apply this result to specify corresponding limitations on the occurrence of runs.

Details

Metrics

73 Record Views
18 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.182 Data Structures, Algorithms & Complexity
4.182.1103 Efficient Algorithms
Web Of Science research areas
Mathematics
Mathematics, Applied
ESI research areas
Engineering
Logo image