Int. J. of Information Technology, Communications and Convergence   »   2011 Vol.1, No.3

 

 

Title: On the top-down evaluation of tree inclusion problem

 

Author: Yangjun Chen, Yibin Chen

 

Addresses:
Department of Applied Computer Science, University of Winnipeg, Winnipeg, Manitoba, R3B 2E9, Canada.
Department of Applied Computer Science, University of Winnipeg, Winnipeg, Manitoba, R3B 2E9, Canada

 

Abstract: We consider the following tree-matching problem: Given labelled, ordered trees P and T, can P be obtained from T by deleting nodes. Deleting a node v entails removing all edges incident to v and, if v has a parent u, replacing the edges from u to v by edges from u to the children of v. The best known algorithm for this problem needs O('T'•'leaves(P)') time and O('leaves(P)'•min{DT•'leaves(T)'} + 'T' + 'P') space, where leaves(T) (resp. leaves(P)) stands for the set of the leaves of T (resp. P), and DT(resp. DP) for the height of T (resp. P). In this paper, we present a new algorithm that requires O('T'•'leaves(P)') time but only O('T' + 'P') space.

 

Keywords: ordered labelled trees; tree inclusion; TreeBank; tree matching problem.

 

DOI: 10.1504/IJITCC.2011.042124

 

Int. J. of Information Technology, Communications and Convergence, 2011 Vol.1, No.3, pp.238 - 253

 

Available online: 28 Aug 2011

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article