A CRCW PRAM Lower Bound for Problems on Two Dimensional Arrays

Abstract

An array $A[i,j]$, $1\le i\le n,1\le j\le 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\dots 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{array}{ll}\mathrm{\Theta }\left(\frac{n^2}{p}\right)& \text{if }p\le \frac{n^2}{\log \log n},n>{17}^3(1.1)\\ \mathrm{\Theta }(\log \log n)& \text{if }\frac{n^2}{\log \log n}<p{17}^3(1.2)\\ \mathrm{\Theta }(\log {\log }_{\frac{2p}{n^2}}p)& \text{if }{n}^2\le p{17}^3(1.3)\\ \mathrm{\Theta }(\log {\log }_{\frac{2p}{n^2}}p)& \text{if }{n}^2{\log }^{2}n\le p\le n^4,n\text{ large enough}(1.4)\end{array}$$