On the tree inclusion problem

We consider the following problem: Given ordered labeled trees S and T can S be obtained from T by deleting nodes?' Deletion of the root node u of a s ubtree with children (T-1,...,T-n) means replacing the subtree by the trees T-1,...,T-n. For the tree inclusion problem, there can generally be expone ntially many ways to obtain the included tree. P. Kilpelinen and H. Mannila [5,7] gave an algorithm based on dynamic programming requiring O(\ S \ . \ T \) time and space in the worst case and also on the average for solving this problem. We give an algorithm whose idea is similar to that of [5,7] b ut which improves the previous one and on the average breaks the \S\ . \T\ barrier.