Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1997 Copyright 1997 Universität Bonn, Institut für Informatik, 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 one-to-one map f from the nodes of P to the nodes of T which preserves the labels, the ancestor relation and the left-to-right 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|+#matches-DEPTH(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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V