An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension

Takayoshi SHOUDAI  Tetsuhiro MIYAHARA  Tomoyuki UCHIDA  Satoshi MATSUMOTO  Yusuke SUZUKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1344-1354
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1344
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
tree structured pattern,  graph pattern matching algorithm,  polynomial time algorithm,  NP-completeness,  

Full Text: PDF>>
Buy this Article

A term is a connected acyclic graph (unrooted unordered tree) pattern with structured variables, which are ordered lists of one or more distinct vertices. A variable of a term has a variable label and can be replaced with an arbitrary tree by hyperedge replacement according to the variable label. The dimension of a term is the maximum number of vertices in the variables of it. A term is said to be linear if each variable label in it occurs exactly once. Let T be a tree and t a linear term. In this paper, we study the graph pattern matching problem (GPMP) for T and t, which decides whether or not T is obtained from t by replacing variables in t with some trees. First we show that GPMP for T and t is NP-complete if the dimension of t is greater than or equal to 4. Next we give a polynomial time algorithm for solving GPMP for a tree of bounded degree and a linear term of bounded dimension. Finally we show that GPMP for a tree of arbitrary degree and a linear term of dimension 2 is solvable in polynomial time.