Optimally fast CRCW-PRAM testing 2D-arrays for existence of repetitive patterns

Abstract

In classical combinatorial string matching repetitions and other regularities play a central role. Besides their theoretical importance, repetitions in strings have been found relevant to coding and automata theory, formal languages, data compression, and molecular biology. An important motivation for developing a 2D pattern matching theory is seen in its relation with pattern recognition, image processing, computer vision and multimedia. Repetitions in 2D arrays have been defined and classified recently.(5) In this paper we present an optimally fast CRCW-PRAM algorithm for testing whether a given n x n array contains repetitions of certain type. The algorithm takes optimal O (log log n) time with n(2)log(2)n/log log n processors.