APPROXIMATE MATCHING FOR 2 FAMILIES OF TREES

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.