
University of Bonn > Department of Computer Science > Chair V  
CSReports 1997  Copyright 1997 University of Bonn, Department of Computer Science, Abt. V  
85167

A New Algorithm for the Ordered Tree Inclusion Problem
Thorsten Richter [Download PostScript] [Download PDF] In the problem of ordered tree inclusion two ordered labeled trees P and T are given, and the pattern tree P matches the target tree T at a node x, if there exists a onetoone map f from the nodes of P to the nodes of T which preserves the labels, the ancestor relation and the lefttoright ordering of the nodes. In [12] Kilpeläinen and Mannila give an algorithm that solves the problem of ordered tree inclusion in time and space \Theta(P*T). In this paper we present a new algorithm for the ordered tree inclusion problem with time complexity O(\Sigma_P*T+#matchesDEPTH(T)), where \Sigma_P is the alphabet of the labels of the pattern tree and #matches is the number of pairs (v,w) \in P \times T with LABEL(v)=LABEL(w). The space complexity of our algorithm is O(\Sigma_P*T+#matches). 

Last Change:
08/18/99 at 13:00:38
Deutsch 
University of Bonn > Department of Computer Science > Chair V 