Menu
An array \(A[i, j]\), \(1 \leq i \leq n, 1 \leq j \leq n\), has a period \(A[p,p]\) of dimension \(p \times p\) if \(A[i, j] = A[i+p, j+p]\) for \(i, j = 1 \ldots n-p\). The period of \(A_{p,p}\) is the shortest such \(p\).
We study two-dimensional pattern matching, and several other related problems, all of which depend on finding the period of an array.
In summary, finding the period of an array in parallel using \(p\) processors for general alphabets has the following bounds:
\[
\begin{cases}
\Theta\left(\frac{n^2}{p}\right) & \text{if } p \leq \frac{n^2}{\log \log n}, n>17^3 \quad\quad\quad\quad\quad\quad\quad\quad(1.1) \\
\Theta(\log\log n) & \text{if } \frac{n^2}{\log \log n} < p 17^3 \quad\;\; \quad\quad\quad\quad (1.2) \\
\Theta\left(\log\log_{\frac{2p}{n^2}}{p}\right) & \text{if } n^2 \leq p 17^3 \quad \quad\quad\quad\quad (1.3) \\
\Theta\left(\log\log_{\frac{2p}{n^2}}{p}\right) & \text{if } n^2 \log^2 n \leq p \leq n^4, \text{ $n$ large enough} \quad (1.4)
\end{cases}
\]