Parallel algorithms for term matching

Abstract

We present a randomized parallel algorithm for term matching. Let n be the number of nodes of the directed acyclic graphs (dags) representing the terms to be matched. Then our algorithm uses O(log2 n) parallel time and M(n) processors, where M(n) is the complexity of n×n matrix multiplication. The randomized algorithm is of the Las Vegas type, that is, the answer is always correct, although with small probability the algorithm might fail to produce an answer. The number of processors is a significant improvement over previously known bounds. Under various syntactic restrictions on the form of the input dags, only O(n2) processors are required in order to achieve deterministic O(log2n) parallel time. Furthermore, we reduce directed graph reachability to term matching using constant parallel time and O(n2) processors. This is evidence that no deterministic algorithm can significantly beat the processor bound of our randomized algorithm.