ORDERED AND UNORDERED TREE INCLUSION

The following tree-matching problem is considered: Given labeled trees P and T, can P be obtained from T by deleting nodes? Deleting a node It entails removing all edges incident to u and, if u has a parent v, replacing the edge from v to u by edges from v to the children of u. T he problem is motivated by the study of query languages for structured text databases. Simple solutions to this problem require exponential time. For ordered trees an algorithm is presented that requires O(\P\\ T\) time and space. The corresponding problem for unordered trees is a lso considered and a proof of its NP-completeness is given. An algorit hm is presented for the unordered problem. This algorithm works in O(\ P\\T\) time if the out-degrees of the nodes in P are bounded by a cons tant, and in polynomial time if they are O(log\T\).