We study approximate matching between h-ary trees (ordered trees whose
nodes have exactly h sons) and ordered arbitrary trees, using a strin
g representation of trees. For two h-ary trees P, T, the subtree dista
nce is the number of subtrees to be inserted in P in place of empty no
des, or to be deleted from P, to obtain T. We consider the problem of
finding all the occurrences of P in T, with bounded distance k. A know
n sequential solution requires O(h\P\+h\T\+k\T\) time. We show that th
e problem can be solved in O(log h+log\P\+log\T\+k) parallel time, in
a CRCW-PRAM with O(h(\P\+\T\)) processors. For arbitrary ordered trees
we solve a version of the classical tree pattern matching problem. We
define the leaf distance between two trees P, T as the total number o
f subtrees to be inserted in P in place of its leaves, or to be delete
d from P leaving leaves in their place, to obtain T. We show how all t
he occurrences of P as a subtree of T, with bounded distance k, can be
determined in O(\P\+k\T\) sequential time, and in O(log\P\+log\T\+k)
parallel time in a CRCW-PRAM with O(\P\+\T\) processors. We also discu
ss an extension of the above problems to labelled trees. (C) 1995 Acad
emic Press, Inc.