Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUB-LINEAR:
Reports tagged with sub-linear:
TR04-092 | 3rd November 2004
Oded Lachish, Ilan Newman

#### Testing Periodicity

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},
if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,
$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.
A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,
if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ ... more >>>

ISSN 1433-8092 | Imprint