loading...
On the Algorithm of Berztiss for Tree Pattern Matching
Colima, M?xico September 20-September 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ENC.2004.1342587Fifth Mexican International Conferenc ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Gabriel Valiente, "On the Algorithm of Berztiss for Tree Pattern Matching," Mexican International Conference on Computer Science, pp. 43-49, Fifth Mexican International Conference in Computer Science (ENC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/ENC.2004.1342587,
author = {Gabriel Valiente},
title = {On the Algorithm of Berztiss for Tree Pattern Matching},
journal ={Mexican International Conference on Computer Science},
volume = {0},
year = {2004},
isbn = {0-7695-2160-6},
pages = {43-49},
doi = {http://doi.ieeecomputersociety.org/10.1109/ENC.2004.1342587},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Mexican International Conference on Computer Science
TI - On the Algorithm of Berztiss for Tree Pattern Matching
SN - 0-7695-2160-6
SP43
EP49
A1 - Gabriel Valiente,
PY - 2004
KW - design and analysis of algorithms
KW - combinatorial problems
KW - tree pattern matching
KW - subtree isomorphism
VL - 0
JA - Mexican International Conference on Computer Science
ER -
 
Gabriel Valiente, Technical University of Catalonia
The tree pattern matching problem over labeled trees is addressed in this paper. Several tree pattern matching algorithms are known which are based on the decomposition of the pattern into strings, with each string representing a root-to-leaf path. Among these, Alfs T. Berztiss gave a simple tree pattern matching algorithm which remained unknown to the research community. In this paper, the tree pattern matching algorithm of Berztiss is reviewed, its correctness is established, and its complexity is shown to be O(mn) time and space in the worst case and O(n) on the average, where n is the text size and m is the pattern size.
Index Terms:
design and analysis of algorithms, combinatorial problems, tree pattern matching, subtree isomorphism
Citation:
Gabriel Valiente, "On the Algorithm of Berztiss for Tree Pattern Matching," enc, pp.43-49, Fifth Mexican International Conference in Computer Science (ENC'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.