ON 2-DIMENSIONAL PATTERN-MATCHING BY OPTIMAL PARALLEL ALGORITHMS

Simplified versions of Kedem-Landau-Palem algorithms for parallel one- dimensional and two-dimensional pattern-matching on a CRCW PRAM are pr esented. We show that the only nontrivial part of KLP algorithm is the preprocessing part: computation of consistent names of very small fac tors. The crucial part in KLP algorithm is a suffix-prefix matching su bprocedure. In our algorithm such a subprocedure is avoided. A novel a lgorithm for 2-dimensional matching is presented which is more directl y designed for two-dimensional objects. It does not use the multi-text /multi-pattern approach as in KLP algorithm. Techniques for constructi ng parallel image identification algorithms are introduced: cutting im ages into small factors, and compressing images by a parallel reductio n of a large number of such independent factors into smaller objects. The importance of five types of factors is emphasized. A new useful ty pe of two-dimensional factors is introduced: thin factors.