[2O1-GS-3] Knowledge utilization and sharing:

[2O1-GS-3-04] An Ordered Term Tree Pattern Matching Algorithm for Multiple Compressed Ordered Trees

〇Masahiro Yamaguchi¹, Tomoyuki Uchida¹, Yuko Itokawa², Tetsuhiro Miyahara¹, Yusuke Suzuki¹ (1. Hiroshima City University, 2. Hiroshima International University)

Keywords:Graph algorithm, Ordered tree pattern, Multiple compressed ordered tree, Pattern matching

An ordered term tree pattern is an edge-labeled ordered tree that has variables. An ordered term tree pattern that has no variables is an ordered tree. An ordered term tree pattern p is said to match an ordered tree T if T is obtained from p by replacing all of variables in p with arbitrary edge-labeled ordered trees, respectively. An ordered tree obtained by structurally and reversibly multiply compressing T is called with a multiple compressed ordered tree of an ordered tree T. In this paper, given an ordered term tree pattern t and a multiple compressed tree comp(T) of an ordered tree T as input, we propose a matching algorithm to determine whether or not t matches T without explicitly decompressing comp(T). Furthermore, we show the efficiency of our matching algorithm by reporting experimental results obtained by comparing a running time of our matching algorithm for an ordered tree p and a multiple compressed ordered tree T with those of the matching algorithm proposed by Suzuki et al. in 2015 for p and the decompressed ordered tree comp(T).