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 subtree with children means replacing the subtree by the trees . For the tree inclusion problem, there can generally be exponentially many ways to obtain the included tree. P. Kilpelinen and H. Mannila 5,7] gave an algorithm based on dynamic programming requiring 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] but which improves the previous one and on the average breaks the barrier. Received: 4 November 1996 / 2 March 2001