On two-dimensional pattern matching by optimal parallel algorithms

AbstractSimplified versions of Kedem–Landau–Palem algorithms for parallel one-dimensional and two-dimensional pattern-matching on a CRCW PRAM are presented. We show that the only nontrivial part of KLP algorithm is the preprocessing part: computation of consistent names of very small factors. The crucial part in KLP algorithm is a suffix–prefix matching subprocedure. In our algorithm such a subprocedure is avoided. A novel algorithm for 2-dimensional matching is presented which is more directly designed for two-dimensional objects. It does not use the multi-text/multi-pattern approach as in KLP algorithm. Techniques for constructing parallel image identification algorithms are introduced: cutting images into small factors, and compressing images by a parallel reduction of a large number of such independent factors into smaller objects. The importance of five types of factors is emphasized. A new useful type of two-dimensional factors is introduced: thin factors