Khalid Abdulla, Andrew Wirth, et al.
ICIAfS 2014
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.
Khalid Abdulla, Andrew Wirth, et al.
ICIAfS 2014
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
Eric Price, David P. Woodruff
FOCS 2011
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007