Raymond Wu, Jie Lu
ITA Conference 2007
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.
Raymond Wu, Jie Lu
ITA Conference 2007
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Robert E. Donovan
INTERSPEECH - Eurospeech 2001
Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems