Term Matching on Parallel Computers

Term matching is an important problem that arises very often in term rewriting and in functional and equational programming. We present a new parallel algorithm for the term-matching problem on the EREW (exclusive read, exclusive write) model of parallel computation. Our algorithm assumes a string representation of the two terms as its input. The string representation is first transformed into two labeled ordered trees, and term matching is then performed on these two trees. If n is the length of the input terms, then for any constant ε (0 < ε ≤ 1) our algorithm uses O(n ^1-ε ) processors and takes O(n ^ε logn) time. If ε = 0, the same algorithm will run in O(log ² n) time. The only other known parallel algorithm for this problem, due to Dwork, Kanellakis, and Stockmeyer, requires O(n ² ) processors and takes either O(logn) or O(log ² n) time. However, their algorithm uses the stronger CREW (concurrent read, exclusive write) model of parallel computation and assumes a DAG (directed acyclic graph) representation of the two terms as its input. On the CRCW (concurrent read, concurrent write) model our algorithm requires n processors and O(log n) time.