Al. Delcher et S. Kasif, TERM MATCHING ON A MESH-CONNECTED ARRAY OF PROCESSORS, Annals of mathematics and artificial intelligence, 14(2-4), 1995, pp. 177-186
In this paper, we present a parallel algorithm for term matching of lo
gical terms on a mesh-connected array of processors. Term matching is
a special case of unification in which one of the terms is fully groun
d, i.e. contains no variables. Term matching is a fundamental computat
ional primitive in automated reasoning and has wide applicability to l
ogic programming and symbolic pattern matching. Our algorithm runs in
O(root N) time on a root N x root N two-dimensional mesh-connected arr
ay of processors.