@inproceedings{oai:soar-ir.repo.nii.ac.jp:00012448,
 author = {Yamamoto,  Hiroaki and Takenouchi,  Daichi},
 book = {Lecture Notes in Computer Science},
 month = {},
 note = {Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009., The following tree pattern matching problem is considered: Given two unordered labeled trees P and T, find all occurrences of P in T. Here P and T are called a pattern tree and a target tree, respectively. We first introduce a new problem called the pseudo-tree pattern matching problem. Then we show two efficient bit-parallel algorithms for the pseudo-tree pattern matching problem. One runs in O(L(P).n.l. [h/w]) time and O(n.l.[h/w]) space, and another one runs in O((L(P).n+h.2(l)).[h.l/W]) time and O((n + h.2(l)).[h.l/W]) space, where n is the number of nodes in T, h and l are the height of P and the number of leaves of P, respectively, and W is the length of a computer-word. The parameter L(P), called a recursive level of P, is defined to be the number of occurrences of the same label on a path from the root to a leaf. Hence we have L(P) <= h. Finally, we give an algorithm to extract all occurrences from pseud-occurrences in O(n.L(P).l(3/2)) time and O(n.L(P).l) space., Article, Lecture Notes in Computer Science. 5664:554-565 (2009)},
 pages = {554--565},
 publisher = {SPRINGER VERLAG},
 title = {Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees},
 volume = {5664},
 year = {2009}
}